[コンパイラ] 20. 現代コンパイラの発展と応用

ソースコード  フロントエンド   LLVM IR    ミドルエンド    LLVM IR    バックエンド    機械語
                                       （最適化）
C/C++   --> Clang    -->            -->           -->          --> x86
Rust    --> rustc    --> 共通IR    --> 共通最適化  --> 共通IR   --> ARM
Swift   --> swiftc   -->            -->           -->          --> RISC-V
Fortran --> flang    -->            -->           -->          --> WebAssembly

; LLVM IRの例：2つの数の和
define i32 @add(i32 %a, i32 %b) {
entry:
  %result = add i32 %a, %b
  ret i32 %result
}

; 条件文の例
define i32 @max(i32 %a, i32 %b) {
entry:
  %cmp = icmp sgt i32 %a, %b
  br i1 %cmp, label %then, label %else

then:
  br label %merge

else:
  br label %merge

merge:
  %result = phi i32 [%a, %then], [%b, %else]
  ret i32 %result
}

主な最適化パス：
- mem2reg：メモリアクセスをレジスタに昇格（SSA構築）
- instcombine：命令組み合わせ最適化
- gvn：大域的値番号付け
- licm：ループ不変コード移動
- indvars：誘導変数の単純化
- loop-unroll：ループ展開
- inline：関数インライニング
- sccp：希薄条件付き定数伝播
- dce：デッドコード除去
- simplifycfg：制御フローの簡約

-O0：最適化なし（デバッグ用）
-O1：基本最適化（高速コンパイル）
-O2：標準最適化（ほとんどの場合推奨）
-O3：攻撃的最適化（コードサイズ増加を許容）
-Os：コードサイズ最適化
-Oz：極限サイズ最適化

歴史：1987年Richard Stallmanが開始
言語：C、C++、Fortran、Go、Adaなど
特徴：
- 約40年の歴史、広大なアーキテクチャサポート
- GIMPLE（中間表現）-> RTL（低水準表現）の2段階構造
- 強力な最適化（特にFortran）
- GPLライセンス

歴史：2003年Chris Lattnerが開始（UIUC）
Clang：LLVMのC/C++/Objective-Cフロントエンド
特徴：
- モジュール化されたライブラリ設計
- より良いエラーメッセージ
- 高速なコンパイル速度
- Apache 2.0ライセンス（商用利用に有利）
- IDE統合が容易（libclang、clangd）

AOT（Ahead-Of-Time）コンパイル：
  ソースコード -> [コンパイル] -> 機械語 -> [実行]
  例：C/C++（gcc、clang）、Rust、Go

JIT（Just-In-Time）コンパイル：
  ソースコード -> [インタプリタで実行開始] -> [ホットスポット検出] -> [実行中にコンパイル] -> [最適化コードに切替]
  例：Java（HotSpot）、JavaScript（V8）、.NET（RyuJIT）

// 1. プロファイルベース最適化（PGO）
// 実行中に収集した情報で最適化を決定
if (type == "string") {   // 95%の場合true
    // JIT：この分岐を最適化（インラインキャッシュ）
}

// 2. 投機的最適化（Speculative Optimization）
// 仮定が正しい間高速コードを実行
// 仮定が外れたら脱最適化（deoptimization）後インタプリタに復帰

// 3. 適応的最適化（Adaptive Optimization）
// ホットなコードのみ最適化、コールドコードはインタプリタで実行
// コンパイル時間と実行時間のバランス

実行フロー：
1. バイトコードインタプリタで開始
2. 呼び出し回数が閾値を超えたらC1コンパイラ（高速コンパイル、簡単な最適化）
3. さらに多く実行されたらC2コンパイラ（低速コンパイル、攻撃的最適化）

階層的コンパイル（Tiered Compilation）：
Level 0：インタプリタ
Level 1：C1（プロファイリングなし）
Level 2：C1（制限的プロファイリング）
Level 3：C1（全体プロファイリング）
Level 4：C2（最適化コード）

実行フロー：
1. パーサ：JavaScript -> AST
2. Ignition（インタプリタ）：AST -> バイトコード実行
3. Sparkplug（ベースラインJIT）：高速機械語生成
4. Maglev（中間層JIT）：中間レベル最適化
5. TurboFan（最適化JIT）：攻撃的最適化

核心技法：
- Hidden Classes：動的型オブジェクトに構造を付与
- Inline Caching：プロパティアクセスの最適化
- Deoptimization：投機が外れたらインタプリタに復帰

// ジェネリクス実装戦略：

// 1. 単相化（Monomorphization）- Rust、C++
//    各具体型に対して別個のコードを生成
//    利点：高速実行（インライニング、特化最適化）
//    欠点：コードサイズ増加（code bloat）

// 2. 型消去（Type Erasure）- Java、Kotlin
//    コンパイル時にジェネリクス型情報を除去、Objectとして処理
//    利点：コードサイズが小さい
//    欠点：ボクシング/アンボクシングオーバーヘッド、ランタイム型情報の損失

// 3. 辞書渡し（Dictionary Passing）- Haskell
//    型クラスのメソッドテーブルを引数として渡す
//    利点：コードサイズが小さい
//    欠点：間接呼び出しオーバーヘッド

// クロージャ：自由変数をキャプチャする関数

// コンパイル時の処理：
// 1. キャプチャされた変数を構造体（環境）に格納
// 2. クロージャ = 関数ポインタ + 環境ポインタ

// 例（疑似コード）：
// 元：
// fn make_adder(x):
//     return fn(y): x + y

// コンパイル後：
// struct Env { int x; }
// int closure_fn(Env* env, int y) { return env->x + y; }
// Closure make_adder(int x) {
//     Env* env = alloc(Env);
//     env->x = x;
//     return (closure_fn, env);
// }

// パターンマッチングのコンパイル戦略：

// 1. 決定木（Decision Tree）
//    各パターンを順次テスト
//    検査回数を最小化するようツリーを構成

// 2. バックトラッキングオートマトン
//    複数のパターンを同時にマッチング
//    メモリ効率的だが実装が複雑

// 例：
// match value {
//     (0, y) => ...,
//     (x, 0) => ...,
//     (x, y) => ...,
// }
//
// 決定木：
//   value.0 == 0?
//     yes -> パターン1（y = value.1）
//     no  -> value.1 == 0?
//              yes -> パターン2（x = value.0）
//              no  -> パターン3（x = value.0, y = value.1）

主な静的解析ツール：
- Clang Static Analyzer：パス感度分析、メモリバグ検出
- Coverity：商用静的解析ツール
- Infer（Meta）：大規模コードベースでのメモリ安全性検査
- CodeQL（GitHub）：クエリベースコード分析

検出可能な問題：
- NULLポインタ逆参照
- バッファオーバーフロー
- メモリリーク
- 解放後使用（use-after-free）
- データレース

主なサニタイザ（LLVM/GCC対応）：

AddressSanitizer（ASan）：
- メモリアクセスエラー検出（バッファオーバーフロー、use-after-free）
- 約2倍の性能オーバーヘッド
- コンパイル：clang -fsanitize=address

MemorySanitizer（MSan）：
- 未初期化メモリ読み取りの検出
- 約3倍の性能オーバーヘッド

ThreadSanitizer（TSan）：
- データレースの検出
- 約5-15倍の性能オーバーヘッド

UndefinedBehaviorSanitizer（UBSan）：
- 未定義動作の検出（整数オーバーフロー、不正なシフトなど）
- 最小限の性能オーバーヘッド

// 元のコード：
int a[10];
a[15] = 42;  // バッファオーバーフロー！

// ASanが挿入するコード（概念的）：
// 1. メモリ周辺に「レッドゾーン」を設定
// 2. すべてのメモリアクセス前に境界検査
// 3. アクセスがレッドゾーンに触れたらエラー報告

// 実行時出力：
// ERROR: AddressSanitizer: stack-buffer-overflow
// WRITE of size 4 at address ...
// [スタックトレース]

// 制御フロー完全性（LLVM CFI）：
// 関数ポインタを通じた呼び出しが有効な対象のみ呼び出すよう検証

// clang -fsanitize=cfi
// 間接呼び出し時に対象関数のシグネチャを検証

従来の方式：
  PyTorch/TensorFlow -> フレームワークランタイム -> cuDNN/MKL -> GPU/CPU

コンパイラ方式：
  モデル定義 -> グラフIR -> 最適化 -> コード生成 -> GPU/CPU/TPU/NPU

利点：
- ハードウェア特化最適化の自動化
- 新ハードウェアへの迅速なサポート
- 演算融合（operator fusion）によるメモリアクセスの最小化

XLAの最適化：
1. 演算融合（Operation Fusion）
   - 複数の要素別演算を一つのカーネルに統合
   - 中間テンソルのメモリ割り当てを除去

2. レイアウト最適化
   - テンソルのメモリレイアウトをハードウェアに最適化

3. 定数畳み込み
   - コンパイル時に決定可能なテンソル演算を事前計算

TVMスタック：
  フロントエンド：PyTorch、TensorFlow、ONNXモデルの取り込み
       |
  Relay IR：高水準グラフ表現
       |
  Relay最適化：グラフレベル最適化（融合、量子化など）
       |
  Tensor IR（TIR）：低水準テンソル演算表現
       |
  AutoTVM/Ansor：自動性能チューニング（スケジュール探索）
       |
  コード生成：CUDA、OpenCL、Metal、LLVMなど

- MLIR（Multi-Level IR）：LLVMプロジェクトの多階層IRフレームワーク
  様々な抽象化レベルをサポートする統合コンパイラインフラ

- Triton：GPUカーネル作成のためのPythonベース言語/コンパイラ
  PyTorch 2.0のtorch.compileバックエンド

- IREE：MLモデルを組み込み/モバイル環境にデプロイするためのコンパイラ

- StableHLO：MLモデルの移植可能なシリアライズ形式

特徴：
- スタックベース仮想マシン
- 静的型システム
- メモリ安全（線形メモリモデル）
- 多様な言語からコンパイル対象として使用可能
- ブラウザだけでなくサーバ、組み込みでも使用拡大

C/C++   -> Emscripten -> LLVM -> Wasmバックエンド -> .wasm
Rust    -> rustc      -> LLVM -> Wasmバックエンド -> .wasm
Go      -> TinyGo     -> LLVM -> Wasmバックエンド -> .wasm
Kotlin  -> Kotlin/Wasm                           -> .wasm

;; WAT（WebAssembly Text Format）の例：フィボナッチ
(module
  (func $fib (param $n i32) (result i32)
    (if (i32.lt_s (local.get $n) (i32.const 2))
      (then (return (local.get $n)))
    )
    (i32.add
      (call $fib (i32.sub (local.get $n) (i32.const 1)))
      (call $fib (i32.sub (local.get $n) (i32.const 2)))
    )
  )
  (export "fib" (func $fib))
)

主な課題：
1. GC統合：参照型とGCサポート（Wasm GC提案）
2. SIMD：ベクトル演算サポート（128ビットSIMD実装済み）
3. スレッド：共有メモリと原子的演算
4. 例外処理：ゼロコスト例外処理
5. 末尾呼び出し：関数型言語サポート

最適化ツール：
- Binaryen：Wasm特化最適化（wasm-opt）
  - デッドコード除去
  - 関数インライニング
  - 定数畳み込み
  - コードサイズ最適化

応用分野：
- サーバレスコンピューティング：Cloudflare Workers、Fastly Compute
- コンテナ代替：Docker + Wasm
- プラグインシステム：安全な拡張実行環境
- 組み込みシステム：リソース制限環境

1. AIベースコンパイラ最適化
   - 強化学習による最適化パス順序決定
   - ニューラルネットワークベースのレジスタ割り当て
   - LLMベースのコード分析と最適化提案

2. ドメイン特化コンパイラ（DSLコンパイラ）
   - 特定分野（ML、グラフ、データベース）に最適化されたコンパイラ
   - Halide（画像処理）、GraphIt（グラフアルゴリズム）

3. 検証済みコンパイラ（Verified Compiler）
   - CompCert：数学的に検証されたCコンパイラ
   - 最適化の正当性を形式的に証明

4. 異種コンピューティングサポート
   - CPU + GPU + FPGA + NPUを統合管理するコンパイラ
   - SYCL、OneAPI（Intel）などの標準

5. セキュリティ内蔵コンパイラ
   - メモリ安全言語（Rust）の普及
   - ハードウェアセキュリティ機能（ARM MTE、Intel CET）の活用