9 分で読了 #compilers #intermediate-representation
このページの目次

LLVM IR 実践

LLVM IR は SSA の教科書的な例に留まらない——Clang、Rustc、Swiftc など数十のコンパイラフロントエンドが共有する「ターゲット言語」であり、完全なSSA、強型付け、3アドレスコードである。IRの構文とメモリモデルを理解して初めて、ASTからLLVMへのコード生成を自前で実装できる。

概要

SSA形式では、SSAの数学的基盤——支配木/φ関数/Cytronアルゴリズム——について解説した。ここではLLVM IRに焦点を当て、LLVMの中間表現としての側面、すなわち完全なSSA、強型付け、3アドレスコード形式であることを説明する。これはClang、Rustc、Swiftcなど数十のコンパイラフロントエンドの共通ターゲットであり、LLVM最適化パイプラインへの入力でもある。本稿では「LLVMにはどのようなpassがあるか」ではなく、LLVM IRという言語としての構文、セマンティクス、型、メモリモデルについて述べる——これらを理解して初めて、「ASTからLLVM IRへの降下（lowering）」を自前で実装できる。

LLVM IRの3つの形式

同じLLVMモジュールには3つの表現があり、これらは互いに同等である：

.ll (人間可読テキスト):         ドキュメントやデバッグで目にする
  %result = add i32 %a, %b
  ret i32 %result

.bc (ビットコードバイナリ):      リンクやLTO（リンク時最適化）に使用されるコンパクトな形式
  (バイナリシーケンス)

メモリIR (C++ API):             コンパイラフロントエンドがメモリ上で構築
  auto *add = builder.CreateAdd(a, b, "result");

3つの形式は llvm-as / llvm-dis / opt / llc によって相互に変換できる。.ll テキスト形式を理解することは、LLVM IRの読解やデバッグの前提条件である。

コア構文：仮想レジスタ + 型 + 命令

仮想レジスタと代入

LLVM IRは完全なSSA——各仮想レジスタ（%1, %2, ... または %name）はちょうど1回だけ代入される：

%x = add i32 1, 2          ; %x が定義される
%y = mul i32 %x, 3          ; %x が使用され、%y が定義される
; %x に再度代入することはできない — SSA違反となるため、φ関数または別のバージョンを使用する必要がある

型システム

LLVM IRの型はCよりもはるかに豊富で明確であり、すべての値に型が存在する：

i1          ; 1ビット整数 (ブール)
i32         ; 32ビット整数
i64         ; 64ビット整数
float       ; 32ビットIEEE浮動小数点数
double      ; 64ビットIEEE浮動小数点数
ptr         ; 不透明ポインタ (opaque pointer, LLVM 15以降)
            ; 旧版: i32* (i32へのポインタ)

[10 x i32]  ; i32が10個並んだ配列
{ i32, float, i8 }   ; 構造体 (匿名)
<4 x float>           ; floatが4個並んだベクトル (SIMD)

不透明ポインタ（ptr）は重要な簡略化である⁠。LLVM 15以前、ポインタは i32*、float** などで表されていた——型とポインタのビット幅は直交していた。不透明ポインタは「ポインタがどの型を指しているか」というエンコーディングを排除し、IRをより簡潔にした（bitcast の使用が減少した）が、フロントエンドは gep に使用するための型情報を自前で維持する必要がある。

制御流命令

LLVM IRの制御流は基本ブロックと終端命令に基づいている：

define i32 @max(i32 %a, i32 %b) {
entry:
  %cond = icmp sgt i32 %a, %b       ; 符号付き比較: 大きい → i1
  br i1 %cond, label %then, label %else

then:
  ret i32 %a                         ; 終端: 戻り値

else:
  ret i32 %b
}
  • br i1 %cond, label %true, label %false: 条件分岐
  • br label %dest: 無条件ジャンプ
  • ret <ty> <value> / ret void: 戻り値
  • switch i32 %val, label %default [...]: 多路ジャンプ
  • indirectbr: 計算によるジャンプ（仮想関数テーブルのディスパッチなど）

Phi命令：制御流の合流点での値選択

define i32 @abs(i32 %x) {
entry:
  %ge = icmp sge i32 %x, 0
  br i1 %ge, label %pos, label %neg

pos:
  br label %merge

neg:
  %negx = sub i32 0, %x
  br label %merge

merge:
  %result = phi i32 [ %x, %pos ], [ %negx, %neg ]
  ; result = posから来たら %x、negから来たら %negx
  ret i32 %result
}

phi引数の [value, predecessor_block] は厳密に束縛される——最初の value は最初の前驱ブロックからの流入に対応する。phi命令は基本ブロックの先頭に配置され、複数のphiの間は宣言順に並ぶ——これらは実際の計算を表すものではなく、制御流の合流点での値選択であり、すべてがそのブロックに入る前（つまり前驱ブロック内）の変数バージョンを参照する。

メモリモデル: alloca / load / store / gep

LLVM IRは仮想レジスタ⁠（SSA値、レジスタ上）とメモリ⁠（スタック/ヒープ上、ポインタ経由でアクセス）を区別する：

%ptr = alloca i32               ; スタック上に i32 を割り当て (ptr を返す)
store i32 42, ptr %ptr          ; ptr が指すメモリに 42 を書き込む
%val = load i32, ptr %ptr       ; ptr から読み戻し → %val (i32)

%x = add i32 %val, 1            ; SSA値に対して直接演算
store i32 %x, ptr %ptr

alloca の結果は ptr であり、その後の load/store は明示的にメモリを読み書きする。LLVMの mem2reg pass は「昇格可能な alloca + load/store のペア」をSSA仮想レジスタとphiに変換する⁠——これは最適化パイプラインに入る前の第一関門であり、昇格不可能な（アドレスが取得される、関数を跨いで渡されるなど）ものはメモリに残る。

GEP (GetElementPtr): 構造体/配列のアドレス計算

getelementptr はLLVM IRの中で最も混乱を招きやすい命令であり、そのセマンティクスは純粋なアドレス計算であり、メモリにアクセスしないことである：

%struct = type { i32, float, i8 }           ; 構造体の定義

%p = alloca %struct
%field1_addr = getelementptr %struct, ptr %p, i32 0, i32 1
;                                            ^^  ^^   ^^
;                                         type  ptr  インデックス:
;                                                  [0]=間接参照なし, [1]=1番目のフィールド (float)
store float 3.14, ptr %field1_addr

GEPの計算は型レイアウトに基づいて完全に行われる——[i32 0, i32 1] とは、「%p から出発し、%struct という型に対して、0番目の要素（ポインタを変更しない）、1番目のフィールドを取る」ことを意味する。GEPはメモリにアクセスするのではなく、ベースアドレスからのオフセットポインタ（構造体フィールドの型レイアウトによって決定される）を返す。i32 は4バイト、float は4バイト境界にアライン、i8 は1バイトである。

現代のLLVMの不透明ポインタでは、GEPの最初のインデックスは通常常に i32 0 である（歴史的なポインタの間接参照はno-opとなった）。

関数とモジュール構造

; 外部宣言
declare i32 @printf(ptr, ...)

; 関数定義
define i32 @main(i32 %argc, ptr %argv) {
  ...
  %fmt = ... ; "Hello %s\n" を指すポインタ
  call i32 (ptr, ...) @printf(ptr %fmt, ptr %str)
  ret i32 0
}
  • @name: グローバルシンボル（関数、グローバル変数）
  • %name: ローカル仮想レジスタ
  • call: 呼び出し——直接呼び出し、間接呼び出し（call i32 %fp(...)）、末尾呼び出し（musttail call）が可能

ASTからLLVM IRへ：1つの降下パス

a + b * c を例に、ASTからLLVM IRへの降下プロセスを示す：

AST:  Binary(+, Variable("a"), Binary(*, Variable("b"), Variable("c")))

コード生成 (再帰的):
  codegen(Binary(+, lhs, rhs)):
    left_val  = codegen(lhs)         → %a = load i32, ptr %a_addr
    right_val = codegen(rhs)        → 再帰:
                                        b_val = codegen(Var("b")) → %b = load...
                                        c_val = codegen(Var("c")) → %c = load...
                                        → %tmp = mul i32 %b, %c
    → %add = add i32 %a, %tmp
    return %add

出力されるLLVM IR:
  %a = load i32, ptr %a_addr
  %b = load i32, ptr %b_addr
  %c = load i32, ptr %c_addr
  %tmp = mul i32 %b, %c
  %add = add i32 %a, %tmp

実際のコード生成では以下も処理する必要がある：

  • ショートサーキット評価 (a && b): if a { if b { true } else { false } else { false } } の制御流 + phiに変換する。
  • 変数のアドレス (&x): xが以前にallocaされていた場合は、そのptrを直接使用する。xがmem2regによって仮想レジスタに昇格されていた場合は、再度allocaしてstoreする必要がある。
  • 集約型⁠: 構造体と配列の代入は、memcpyまたはフィールドごとのload/storeに変換される。

参考

  • LLVM Language Reference Manual: https://llvm.org/docs/LangRef.html — IRの完全な構文とセマンティクス。公式を基準とする。
  • LLVM Kaleidoscope Tutorial: https://llvm.org/docs/tutorial/ — ゼロからDSLをLLVM IRへ実装する
  • "Learn LLVM 17"(Kai Nacke) — LLVMコアのエンジニアリングガイド。passマネージャ、バックエンド、JITを含む

Keywords: LLVM IR, SSA, virtual register, i1, i32, i64, ptr, opaque pointer, struct, array, vector, phi, br, switch, alloca, load, store, gep, getelementptr, bitcast, function, module, intrinsic, lowering, mem2reg, Kaleidoscope

関連ページ

© 2026 liz's doc