2026-08-26·無料·13分で読めます

コンパイラを1から — ソースが機械語になるまで

たった1行の式が、字句解析・構文解析・意味解析・中間表現・最適化・コード生成の6工程を通って1命令の機械語になるまでを、前提知識ゼロから追い切ります。なぜ -O2 でバグが表に出るのか、なぜベンチマークのループが消えるのかも、この道筋の上で説明できます。

#compiler #parsing #optimization #code-generation #systems

対象textタスクsystems

翻訳者と通訳

通訳は喋られた端から訳すので速いけれど、いま聞こえた一文しか材料がありません。翻訳者は原稿を一冊受け取ってから訳すので遅い代わりに、最後まで読んだうえで推敲できます。

インタプリタが通訳、コンパイラが翻訳者です。コンパイラが速いコードを吐けるのは、頭がいいからというより全体を先に見渡してから出力する立場にいるからです。以下で見る「最適化」は、その推敲の中身にほかなりません。

今日ずっと追いかける1行

int f(int x) { return (x + 1) * 4 - 4; }

人間の読み方は「x に1を足して、4倍して、4を引く」— 計算3回です。ところが最適化を効かせると、この関数は計算1回ぶんの機械語になります。どこで3回が1回に減るのかを、6つの段を降りながら追います。

段の名前は字句解析 → 構文解析 → 意味解析 → 中間表現 → 最適化 → コード生成。前半3つを「フロントエンド」、後半を「バックエンド」と呼びます。この境目は実用上効きます。言語 M 個 × CPU N 種類なら素朴には M×N 個の翻訳器が要りますが、共通の中間表現でつなげば M+N 個で済む。LLVM が広く使われている理由の一つがこれです。

第1段字句解析 — 文字の列を単語に切る

コンパイラが最初に受け取るのはただの文字の列です。これを意味の最小単位であるトークンに切り分け、空白とコメントを捨てます。

( ident:x ) ( op:+ ) ( num:1 ) ( op:* ) ( num:4 ) ( op:- ) ( num:4 )

素朴な作業に見えて、1つだけ流儀があります。最長一致（maximal munch）— 切れる限りいちばん長く切る、です。C で a+++b と書くと、字句解析器は + を1つ見た時点で止まらず ++ まで飲み込み、a ++ + b と切ります。作者が a + (++b) のつもりでも通りません。切り方を決めるのは意図ではなく規則で、しかもその規則は構文の知識をまったく使いません。

実装は、正規表現で書いたトークン定義を状態機械に変えたもの。文字を1つ読むごとに状態を1つ進めるだけなので、入力の長さに比例した時間で終わります。

import re
TOKEN = re.compile(r"\s*(?:(\d+)|([A-Za-z_]\w*)|([-+*/()]))")

def lex(src):
    pos = 0
    while pos < len(src):
        m = TOKEN.match(src, pos)
        if not m: raise SyntaxError(src[pos])
        pos = m.end()
        num, ident, op = m.groups()
        yield ("num", int(num)) if num else ("id", ident) if ident else ("op", op)

第2段構文解析 — 並びに構造を与える

トークン列は平らです。x + 1 * 4 を左から順に計算すると (x+1)*4 になりますが、正解は x + (1*4)。この優先順位と結合の向きを並びから復元して木に組み直すのが構文解析です。言語の構造は文法として書かれます。

E \to E + T \mid E - T \mid T, \qquad T \to T * F \mid T / F \mid F, \qquad F \to (\,E\,) \mid \text{num} \mid \text{id}

(1)

矢印は「左のものは右のいずれかの形をしている」と読みます。式( $E$ )は「式 + 項」か項( $T$ )そのもの、項は「項 × 因子」か因子( $F$ )そのもの、因子は括弧か数か名前。この3段の入れ子だけで、掛け算が足し算より深い位置に来ることが強制されます。優先順位は文法の階層そのものです。つまりこの3行が言っているのは、「掛け算と割り算は、足し算と引き算より内側に閉じ込める」という、私たちが手で括弧を書くときの感覚そのものです。

式(1)を素直にコードへ落とすと、関数の入れ子がそのまま文法の階層になります。これが再帰下降構文解析です。

def parse_expr(ts):                 # E → T (('+'|'-') T)*
    node = parse_term(ts)
    while ts.peek() in ("+", "-"):
        op = ts.next()
        node = ("binop", op, node, parse_term(ts))   # 左に積む＝左結合
    return node

while で左へ積み上げているのが、a - b - c を (a-b)-c と解釈させている正体です。ここを再帰にすると右結合になり、引き算の意味が変わります。出口は抽象構文木（AST）。

        (-)
       /   \
     (*)    4
    /   \
  (+)    4
 /   \
x     1

第3段意味解析 — 名前と型を確かめる

木ができても「意味が通るか」はまだ誰も見ていません。x は宣言されているか、int と 4 を掛けてよいか、戻り値の型と合うか。この確認を意味解析が行い、材料としてシンボルテーブル（名前 → 型・宣言位置・スコープの対応表）を作ります。日常で目にするコンパイルエラーの大半はこの段の出力です。

逆に言えば、ここを通ったコードは「文法的に正しく、名前と型に矛盾がない」ところまでしか保証されていません。正しく動く保証ではないこの差が、後で効いてきます。抜けた木は各ノードに型が書き込まれ、バックエンドはそれを見て使う命令を決めます。

第4段中間表現 — 木を1手ずつの命令に崩す

CPUは1手ずつしか実行できないので、木を1行1演算の並びに崩します。これが三番地コードと呼ばれる中間表現です。

t1 = x  + 1
t2 = t1 * 4
t3 = t2 - 4
ret t3

t1〜t3 は仮想レジスタです。本物は十数本しかありませんが、この段では無限にあることにしておきます。

現代のコンパイラがここでほぼ必ずかける制約がSSA形式（静的単一代入）— 「どの変数もちょうど1回しか代入されない」書き方です。嬉しいのは、t2 を見たときに「この値はどこで作られたか」の答えが必ず1箇所に定まること。素朴な書き方では x が何度も上書きされ、その探索が毎回発生します。分岐が合流して値が2通りありうる地点には $\phi$ 関数を置きます。

第5段最適化 — 意味を変えずに短くする

いよいよ推敲ですが、変えてよい範囲は厳密に決まっています。

\forall x \in \text{Input}:\quad \mathrm{obs}\big(P(x)\big) = \mathrm{obs}\big(P'(x)\big)

(2)

「元のプログラム $P$ とその書き換え $P'$ は、どんな入力に対しても、外から観測できる振る舞いが一致していなければならない」。 $\mathrm{obs}$ （observable）が指すのは画面出力、メモリやファイルへの書き込み、システムコールなど。逆に言えば観測できないものは何をしてもよい。途中の計算を消しても順序を入れ替えても、外から見て同じなら合法 — C++ でいう as-if ルールです。つまりこの式は、コンパイラに渡された「外から見て同じなら、中身は自由に作り替えてよい」という一枚の免許状で、 $\mathrm{obs}$ の外側に違いがはみ出した瞬間に免許違反になる、ということを言っています。

この免許を持って、書き換えが順番に走ります。

定数畳み込み: 3 * 4 をコンパイル時に 12 にする
定数伝播: 定数と分かった変数を使用箇所に流し込む
共通部分式削除: 同じ計算が2回あれば1回にして使い回す
デッドコード削除: 結果が誰にも使われない計算を消す
インライン展開: 小さい関数の中身を呼び出し側に貼る
強度削減: 重い演算を軽い演算に置き換える

追いかけている式で起きるのは、代数的な整理と強度削減です。

(x+1)\cdot 4 - 4 \;=\; 4x + 4 - 4 \;=\; 4x \;=\; x \ll 2

(3)

括弧を展開し、+4 と −4 が打ち消し合い、残った 4x を「2ビット左シフト」に置き換えた、という変形です。 $\ll$ はビットを左へずらす演算で、2進数を1桁ずらすと2倍、2桁で4倍。掛け算器を使わずに済み、中間表現は3行から1行に縮みます。つまり、「1を足して4倍して4を引く」と「4倍する」は $x$ に何を入れても同じ答えになり、その4倍はビットを2つ左へずらすだけで足りる、ということです。

t1 = x << 2
ret t1

整数の掛け算と足し算は結合則・分配則を満たすのでこの変形は成り立ちますが、浮動小数点数では成り立ちません。丸め誤差のため $(a+b)+c$ と $a+(b+c)$ は一般に別の値になり、コンパイラは既定でこの並べ替えを禁じています（-ffast-math はその禁を解くスイッチ）。同じ「代数的に等しい」でも整数と浮動小数点で扱いが違うのが、この段でいちばん誤解されやすい点です。

なぜ「いちばん良いコード」を探しに行かないのか

「ありうる命令列を全部試して短いものを選べばいいのでは?」— だめな理由は計算量です。候補は命令数に対して指数的に増えます。

FIG 1命令列を全探索すると O(2ⁿ)。縦軸を線形に切り替えると、n が数十の時点で他の曲線が地面に貼り付いて見えなくなる — コンパイラが「最良」ではなく「十分良い」を狙う理由がここにあります

指数のカーブがどれだけ他と違う生き物かは計算量を1から理解するで扱っています。要点は1つ、コンパイル時間も製品の一部なので、限られた探索で十分良い解を出すことに徹する、です。

とはいえ諦めずに済む場所もあります。式のような木構造に限れば、部分式ごとの最良コードを1度だけ求めて表に貯める動的計画法が効き、全探索の指数が表のマス目の数まで落ちます。

FIG 2図が埋めているのは編集距離の表ですが、「小さい部分問題の答えを1度だけ計算して置き、大きい判断はそれを引くだけにする」呼吸は、命令選択のDPとまったく同じです

この考え方そのものは動的計画法を1から解説で分解しています。

第6段コード生成 — 無限の仮想レジスタを有限の本物に

最後の段の仕事は3つです。

命令選択は、中間表現の断片に実CPUの命令を当てはめます。「4倍」を掛け算命令にするか、シフトにするか、x86-64 なら本来アドレス計算用の lea 命令に肩代わりさせるか。得手不得手はCPUごとに違うので、ここは機種別に持ちます。

レジスタ割り当ては、無限だった t1, t2 … を実レジスタに詰め込みます。定石は干渉グラフの彩色。同時に生きている変数どうしを辺で結び、隣り合う頂点が同じ色にならないよう $k$ 色で塗ります。色がレジスタ、 $k$ がその本数です。この彩色は一般には効率よく解けないため近似で塗り、塗り切れなかった変数はメモリに追い出されます。これがスピル、同時に生きた変数が多すぎる関数が目に見えて遅くなる理由です。

命令スケジューリングは、依存関係を壊さない範囲で順番を入れ替え、CPUの流れ作業が止まらないようにします。なぜ順番で速度が変わるのかはCPUパイプラインと分岐予測の話題です。

追いかけてきた式は、ここまで来ると計算1つと戻りだけになります。arm64（Apple Silicon など）ならおおよそこの形です。

f:
        lsl     w0, w0, #2      // 引数を2ビット左シフト = 4倍
        ret                      // その値を返す

x86-64 なら掛け算命令ではなく lea eax, [rdi*4] のような1命令になります。どちらも3回の計算が1回に畳まれています。信じずに手元で確かめてください。上のCコードを f.c に保存して次を実行すれば、あなたのマシンの本当の出力が出ます。

clang -O0 -S -o - f.c              # 最適化なし: 素直に3回計算する
clang -O2 -S -o - f.c              # 最適化あり: 畳まれた姿
clang -O2 -S -emit-llvm -o - f.c   # 中間表現(LLVM IR)を覗く

-O0 と -O2 を並べて眺めるのが、この記事を自分のものにする最短経路です。ブラウザで済ませたければ Compiler Explorer（https://godbolt.org/）でも同じことができます。

現場ではこう使う

誰が、いつ触るか。 組み込み・ゲーム・数値計算のように1命令が効く領域のエンジニアが、ホットな関数の -S 出力を読みます。ビルド基盤の担当者は -O2 / -Os（サイズ優先）/ -g（デバッグ情報）/ LTO（リンク時最適化）/ PGO（実行プロファイルを食わせた最適化）の組み合わせを決めます。そして近年人口が増えているのがMLコンパイラの担当です。XLA、TVM、torch.compile が計算グラフにやっているのは第4〜6段そのもの — 中間表現に落とし、融合と不要な計算の削除をかけ、GPUカーネルとして吐く。用語が同じなのは偶然ではありません。

知らないと事故になる落とし穴。

未定義動作は最適化の燃料になる。C/C++ の未定義動作は「起きない」と仮定してよいので、ポインタを一度でも参照外しすると、コンパイラは「これは NULL ではない」と結論して後続の NULL チェックを削除できます。-O0 で動いたコードが -O2 で壊れる典型で、Linux カーネルでも実際に起きた事故です。
ベンチマークのループが消える。結果をどこにも使わない計算はデッドコード削除の標的で、空回りするマイクロベンチは測る前に消えていることがあります。結果を volatile 変数に書くか外部関数に渡し、「観測可能」にしてから測ります。
volatile を外さない。メモリマップドI/Oの読み書きは、コンパイラには「同じ番地を何度も読む無駄」に見えます。
-ffast-math を安易に付けない。誤差を打ち消すために順序を工夫した計算が、並べ替えで台無しになります。
デバッグ時の "optimized out"。インライン展開と変数の消去でスタックトレースが飛びます。再現調査は -O1 や -fno-inline に落とすのが定石です。

設計レビューで問われること。 「-O2 にしたら落ちるようになった。何を疑うか」→ まず未定義動作（符号付き整数の桁あふれ、strict aliasing 違反、初期化忘れ）、次に UBSan / ASan。コンパイラのバグを疑うのは最後です。「なぜインライン展開が効くのか」→ 呼び出しの手間が消えるからだけでなく、呼び出し側の情報が中に流れ込んで、定数伝播やデッドコード削除の次の一手が生まれるからです。

まとめ

コンパイラは6段の流れ作業。文字を単語に切り、木に組み、意味を確かめ、1手ずつの命令に崩し、推敲し、機械語にする
推敲が許されるのは「外から観測できる振る舞いが変わらない範囲」だけ。この一線が as-if ルールであり、未定義動作が最適化の燃料になる理由でもある
最良解は諦めている。指数的な探索空間を、動的計画法とヒューリスティクスで十分良いところまで詰めるのが実像
(x+1)*4-4 が1命令になる過程は、clang -O0 -S と clang -O2 -S を並べれば自分の目で確認できる

コンパイラを1から — ソースが機械語になるまで

翻訳者と通訳

今日ずっと追いかける1行

第1段 字句解析 — 文字の列を単語に切る

第2段 構文解析 — 並びに構造を与える

第3段 意味解析 — 名前と型を確かめる

第4段 中間表現 — 木を1手ずつの命令に崩す

第5段 最適化 — 意味を変えずに短くする