著者：lampese
一、 はじめに
コードを書いているとき、まるで「予知能力」があるかのようなツールに好奇心を抱いたことはありませんか？ C/C++ のコンパイラが「変数が初期化されていない可能性があります」と警告したり、TypeScript の IDE があるオブジェクトが「null である可能性があります」と提示したりするとき、それらはプログラムを実行しているのではなく、単にソースコードを「スキャン」することで、潜在的な実行時のリスクを正確に予見しているのです。その背後に隠されているのが、プログラミングの世界における強力かつエレガントな技術 —— 静的解析です。
しかし、多くのアプリケーション開発者にとって、コンパイラや静的解析ツールの仕組みは神秘的なブラックボックスのようなものです。私たちはそれらの恩恵を受けていながら、その内部の設計ロジックや共通のパターンを必ずしも理解しているわけではありません。
本文の目的は、この神秘的なベールを剥がすことです。あなたが普通のアプリケーションを書くプログラマであっても、プログラムの低層原理に興味がある探索者であっても、私たちは一緒に旅に出て、ゼロから理解していきます。なぜ、一見正しく見えるコードが分析ツールに「あら探し」をされるのか？ これらのツールはどのようにして複雑な文法構造から分析可能なロジックを抽出するのか？ そしてさらに重要なことに、なぜそれらはすべて似たような設計哲学を採用しているのか？
私たちは最終的なケーススタディとして、成熟した分析フレームワークである MCIL（MoonBit C Intermediate Language）を取り上げます。新興の AI ネイティブなプログラミング言語である MoonBit が、いかにエレガントに C 言語の静的解析に活用され、高性能でリソースの制約があるシナリオにおいて独自のポテンシャルを発揮するかを提示します。
本文のガイドに従うことで、静的解析の核心的な思想をマスターできるだけでなく、その設計と実装における普遍的な法則を理解できるようになります。マシンにコードの意図を「理解」させ、隠れた欠陥を事前に発見する方法を共に探求しましょう。
二、 私たちがやること
まず、最終的な効果をお見せします。次のようなコードがあると仮定しましょう：
var x
var y = input()
if y > 0 {
x = y + 1
}
return x
これは私たちが自分で設計した簡単な言語です。変数の宣言、代入、if 条件文、while ループ、そして return 文をサポートしており、すべてのブロックは関数スコープ内にあり、ブロックレベルのスコープはありません。
このコードにはバグがあります。変数 x は if の then ブランチでのみ代入されており、else ブランチは空です。もし y <= 0 であれば、プログラムは else ブランチに進みます。このとき x は一度も代入されませんが、return x でその値を使用しようとします。これが「未初期化変数の使用」というエラーですが、コンパイラのレイヤーでは、このコードはロジック的・型的に正しく見えます。
私たちが作成する静的解析器は、このような問題を自動的に検出できます。さらに重要なのは、静的解析器が「なぜ」このように設計されるのか、そしてその設計がいかに分析をシンプルかつ強力にするのかを理解することです。
三、 ソースコードから AST へ：字句解析と構文解析
静的解析を開始する前に、ソースコードを構造化されたデータに変換する必要があります。このプロセスは、字句解析と構文解析の 2 つのステップに分かれます。
-
字句 解析器 （Lexer） は、文字ストリームをトークンストリームに変換します。例えば
var x = 0は、キーワードVar、識別子Ident("x")、代入記号Eq、整数IntLit(0)の 4 つのトークンとして認識されます。字句解析器は文字を先頭から末尾までスキャンし、空白やコメントをスキップし、現在の文字に基づいてどのタイプのトークンを生成するかを決定します。 -
構文 解析器 （ Parser ） は、トークンストリームを抽象構文木（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 には 2 つの重要な特徴があります：
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. 「三番地コード」で複雑な式を置き換える
三番地コードは簡略化された命令形式で、各命令は最大で 3 つの「番地（変数）」しか含みません。例えば 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 の開始時）では、関数の引数のみが「定義済み」であり、ローカル変数はすべて「未定義」です。
-
各代入文は一つの定義を「生成（generate）」します。例えば
x = 0の後、xは「定義済み」になります。 -
各代入文はまた、それ以前の定義を「殺害（kill）」します。例えば
x = 1は、以前のx = 0という定義を無効にします。 -
制御フローの合流点（例えば Block 3 の開始時）では、情報を「マージ」する必要があります。Block 3 には Block 1 から到達する場合もあれば、Block 2 から到達する場合もあります。もしある変数が Block 1 の終わりで「定義済み」であっても、Block 2 の終わりで「未定義」であれば、Block 3 の開始時ではその変数は「未定義の可能性がある」ことになります。
これがデータフロー分析の基本的な考え方です。各基本ブロックのエントリとエグジットに「状態」（この例では「どの変数が定義済みか」という集合）を関連付け、以下を定義します：
-
伝達関数（Transfer Function）：あるブロックのエントリ状態が与えられたとき、エグジット状態をどのように計算するか？ これはブロック内の各命令の効果をシミュレートすることです。
-
マージ関数（Merge Function）：複数のエッジが一点に合流するとき、複数の状態をどのようにマージするか？ 例えば、積集合（「すべての先行ブロックで定義されて初めて定義済みとする」）や、和集合（「いずれかの先行ブロックで定義されていれば定義済みとする」）を取ります。
次に、エントリから開始して、すべてのブロックの状態が変化しなくなる（「不動点」に達する）まで反復を繰り返します。
このプロセスは、一般的なアルゴリズムフレームワークで実装できます：
-
すべてのブロックをワークリストに追加する。
-
ワークリストから一つのブロックを取り出す。
-
先行ブロックの状態とマージ関数に基づき、そのブロックのエントリ状態を計算する。
-
伝達関数に基づき、そのブロックのエグジット状態を計算する。
-
もしエグジット状態が変化したなら、すべての後続ブロックをワークリストに追加する。
-
ワークリストが空になるまで、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 の古い値は不要になります（新しい値を書き込んだため）。したがって、後ろ向き分析では、まず定義を処理（生存性を解消）し、次に使用を処理（生存性を発生）させる必要があります。
マージ関数について、生存変数分析では和集合を使用します。もしある変数が、いずれか一つの出エッジ（out-edge）上で生存しているなら、その変数は現在の地点で生存していることになります。プログラムはいずれの分岐に進む可能性もあり、使用される可能性がある限り、変数は生存し続けなければならないからです。
八、 未初期化変数の検出
では、実用的な分析を実装してみましょう：未初期化の可能性がある変数の検出です。
考え方はこうです：「到達定義分析（Reaching Definitions Analysis）」を用いて、各プログラム地点に到達可能な変数の定義を追跡します。もしある地点で変数を使用しているのに、その地点に到達できる定義が一つも存在しないなら、それは未初期化の使用です。
到達定義分析は前向きです。各代入文は新しい定義を生成し、同時に同一変数の古い定義を殺害します。合流点では、複数のブランチの定義集合の和集合を取ります（いずれの経路の定義も到達する可能性があるため）。
到達定義の情報があれば、検出は直接的です：
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 言語のすべてのトークン（sizeof、typedef、struct、-> など）を処理する必要があります。Parser は、C 言語の完全な文法（関数ポインタ、複合リテラル、指示付き初期化子、GCC 拡張など）を処理する必要があります。cabs2cil 変換は、型推論、暗黙の型変換、定数畳み込み、スコープ解決などを処理する必要があります。
しかし、それらの核心的な分析フレームワークと思想は共通しています。MiniCIL を理解すれば、MCIL のコードを読むのはずっと容易になるでしょう。
以下は、MCIL が C 言語に対して行ったいくつかの簡単な静的解析の例です：
C 言語分析で直面する困難
MCIL に興味がある読者のために、C 言語の静的解析で遭遇する主な困難をいくつか挙げます。これらは非常に重要です：
-
ポインタとエイリアス：先ほどの DSL には単純な変数しかありませんでしたが、C 言語にはポインタがあります。
*p = 1と書いたとき、どの変数を修正しているのでしょうか？ もしpがxまたはyを指す可能性があるなら、この文はいずれかを修正する可能性があります。さらに悪いことに、pとqが同じメモリ領域を指している（エイリアス）可能性があり、*pの修正が*qの値に影響を与えるかもしれません。ポインタの指し先関係を追跡することはエイリアス分析と呼ばれ、静的解析において最も困難な問題の一つです。 -
手続き間分析（Inter-procedural Analysis）：教育用の分析では単一の関数のみを見ていました。しかし、
foo(x)を呼び出したとき、fooはxが指すメモリを修正するでしょうか？ それを解放するでしょうか？ 単一の関数のみを分析する場合、これらの情報はすべて失われます。手続き間分析ではコールグラフを構築し、関数間のデータフローを追跡する必要があります。MCIL は簡単な手続き間分析を実装しており、free(p)後のpの使用を検出できます。 -
複雑な型システム：C 言語の型システムは罠に満ちています。配列のポインタへの退化、関数ポインタの複雑な文法、struct のメモリレイアウト、union の型パンニング（Type Punning）などです。MCIL の
cabs2cil変換はこれらを処理し、統一された形式に正規化します。例えば、すべての暗黙の型変換は明示的なCastEになり、配列からポインタへの変換はStartOfを通じて表現されます。 -
C 言語の未定義動作（UB）：有符号整数のオーバーフロー、ヌルポインタのデリファレンス、境界外アクセス、use-after-free……。C 標準はこれらをすべて「未定義動作」と定義しており、コンパイラはそれらが発生しないと仮定できます。静的解析ツールはこれらの問題を検出する必要がありますが、保守的になりすぎて誤報（False Positive）を出しすぎることも避けなければなりません（一部のロジックはあえてそのような UB を利用して高速化されている場合があるためです）。
十、 まとめ
この記事では、静的解析の基本的な流れを学びました。ソースコードから字句解析、構文解析を経て AST を得て、それを基本ブロックと明示的なジャンプで構成される CFG に変換し、最後にデータフロー分析フレームワークを用いて不動点に達するまで CFG 上で反復させます。私たちは例として生存変数分析と未初期化変数検出を実装し、この静的解析思想の汎用性を示しました。
また、CIL は実は 2000 年代の産物です。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