LLVM入門：コンパイラ基盤の基礎

はじめに

LLVM（Low Level Virtual Machine）は、現代のコンパイラ開発において不可欠な基盤技術です。この記事では、LLVMの基本概念から実際の活用方法まで詳しく解説します。

LLVMとは

LLVMは、コンパイラの中間表現（IR）と最適化、コード生成を提供するオープンソースプロジェクトです。Clang、Rust、Swift、Juliaなど多くの現代的な言語がLLVMをバックエンドとして使用しています。

LLVMプロジェクトの構成

コンポーネント	説明
LLVM Core	中間表現と最適化パス
Clang	C/C++/Objective-Cコンパイラフロントエンド
LLDB	デバッガ
libc++	C++標準ライブラリ
MLIR	マルチレベル中間表現

主な特徴

中間表現（IR）: 機械独立な中間言語
パスベースの最適化: モジュール化された最適化パス
マルチターゲット: x86、ARM、RISC-V、WebAssemblyなど多数のアーキテクチャ対応
SSA形式: 静的単一代入形式による最適化の容易さ

LLVM IRの基本

LLVM IRは、SSA（Static Single Assignment）形式の中間表現です。各変数は一度だけ代入され、制御フロー解析が容易になります。

基本構造

HLJSLLVM

; モジュールの定義
source_filename = "example.c"
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"

; 簡単な関数の例
define i32 @add(i32 %a, i32 %b) {
entry:
  %result = add i32 %a, %b
  ret i32 %result
}

IRの型システム

型	説明
`i1`	1ビット整数（ブール値）
`i8`, `i16`, `i32`, `i64`	整数型
`i128`	128ビット整数
`float`, `double`	浮動小数点数
`ptr`	Opaqueポインタ型（新しい形式）
`[n x type]`	配列型
`{ type1, type2, ... }`	構造体型

制御フロー

HLJSLLVM

; 条件分岐の例
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
}

; ループの例
define i32 @sum_to_n(i32 %n) {
entry:
  br label %loop

loop:
  %i = phi i32 [ 0, %entry ], [ %i.next, %loop ]
  %sum = phi i32 [ 0, %entry ], [ %sum.next, %loop ]
  %i.next = add i32 %i, 1
  %sum.next = add i32 %sum, %i
  %cmp = icmp slt i32 %i.next, %n
  br i1 %cmp, label %loop, label %exit

exit:
  ret i32 %sum.next
}

最適化パス

LLVMは多数の最適化パスを提供しています。これらは独立して適用でき、カスタムパイプラインを構築できます。

代表的な最適化パス

パス名	説明
`-mem2reg`	メモリアロケーションをレジスタに昇格
`-instcombine`	命令の結合・簡略化
`-gvn`	冗長な値の除去（Global Value Numbering）
`-licm`	ループ不変コードの移動
`-inline`	関数のインライン化
`-dce`	デッドコードの除去
`-simplifycfg`	制御フローグラフの簡略化
`-sroa`	アグリゲート型のスカラー化

最適化レベル

HLJSBASH

# 最適化レベルの指定
opt -O0 input.ll -S -o output.ll  # 最適化なし
opt -O1 input.ll -S -o output.ll  # 基本的な最適化
opt -O2 input.ll -S -o output.ll  # 標準的な最適化
opt -O3 input.ll -S -o output.ll  # 積極的な最適化
opt -Os input.ll -S -o output.ll  # コードサイズ重視
opt -Oz input.ll -S -o output.ll  # さらにコードサイズ重視

実践：ClangでIRを生成

CコードからIRへの変換

HLJSC

// example.c
int fibonacci(int n) {
    if (n <= 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
    return fibonacci(10);
}

HLJSBASH

# CコードからLLVM IRを生成
clang -S -emit-llvm example.c -o example.ll

# 最適化を適用したIRを生成
clang -S -emit-llvm -O2 example.c -o example_opt.ll

# 人間が読みやすい形式で生成
clang -S -emit-llvm -O2 -fno-discard-value-names example.c -o example_opt.ll

# 最適化パスの適用
opt -passes='mem2reg,instcombine,gvn,simplifycfg' example.ll -S -o optimized.ll

# アセンブリに変換
llc optimized.ll -o optimized.s

# 実行ファイルの生成
clang optimized.ll -o program

IRの解析

HLJSBASH

# IRの検証
opt -passes=verify example.ll -S -o /dev/null

# CFG（制御フローグラフ）の可視化
opt -passes=dot-cfg example.ll -disable-output
dot cfg.main.dot -Tpng -o cfg.png

# Call Graphの可視化
opt -passes=dot-callgraph example.ll -disable-output
dot callgraph.dot -Tpng -o callgraph.png

Pass Manager

LLVM 13以降、新しいPass Managerが標準となりました。

C++でのパスの実装

HLJSCPP

#include "llvm/IR/Function.h"
#include "llvm/IR/PassManager.h"
#include "llvm/Passes/PassBuilder.h"
#include "llvm/Passes/PassPlugin.h"
#include "llvm/Support/raw_ostream.h"

using namespace llvm;

namespace {

struct MyPass : public PassInfoMixin<MyPass> {
  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM) {
    errs() << "Processing function: " << F.getName() << "\n";
    
    // 関数の解析や変換を行う
    
    return PreservedAnalyses::all();
  }
  
  static bool isRequired() { return true; }
};

}

extern "C" LLVM_ATTRIBUTE_WEAK ::llvm::PassPluginLibraryInfo
llvmGetPassPluginInfo() {
  return {
    LLVM_PLUGIN_API_VERSION, "MyPass", LLVM_VERSION_STRING,
    [](PassBuilder &PB) {
      PB.registerPipelineParsingCallback(
        [](StringRef Name, FunctionPassManager &FPM,
           ArrayRef<PassBuilder::PipelineElement>) {
          if (Name == "my-pass") {
            FPM.addPass(MyPass());
            return true;
          }
          return false;
        });
    }};
}

カスタムパスの使用

HLJSBASH

# パスのビルド
clang -fplugin=./MyPass.so -fpass-plugin=./MyPass.so example.c

# optでの使用
opt -load-pass-plugin=./MyPass.so -passes=my-pass example.ll -S -o output.ll

LLVMのユーティリティ

llc：LLVM静的コンパイラ

HLJSBASH

# ターゲットの指定
llc -march=x86-64 -mcpu=skylake input.ll -o output.s
llc -march=aarch64 input.ll -o output.s
llc -march=riscv64 input.ll -o output.s

# 最適化レベル
llc -O0 input.ll -o output.s
llc -O3 input.ll -o output.s

llvm-dis：IRの逆アセンブル

HLJSBASH

# ビットコードからテキスト形式のIRへ
llvm-dis input.bc -o output.ll

llvm-as：IRのアセンブル

HLJSBASH

# テキスト形式からビットコードへ
llvm-as input.ll -o output.bc

lli：LLVM IRインタプリタ/JIT

HLJSBASH

# IRの直接実行
lli example.ll

# JITの指定
lli -jit-kind=orc example.ll

実践例：簡単な言語の実装

簡易計算機のIR生成

HLJSCPP

#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/Verifier.h"

using namespace llvm;

std::unique_ptr<Module> createCalculatorModule(LLVMContext &Context) {
  auto M = std::make_unique<Module>("calculator", Context);
  IRBuilder<> Builder(Context);
  
  // 関数型の定義
  FunctionType *FT = FunctionType::get(Type::getInt32Ty(Context), {}, false);
  
  // main関数の作成
  Function *F = Function::Create(FT, Function::ExternalLinkage, "main", M.get());
  
  BasicBlock *BB = BasicBlock::Create(Context, "entry", F);
  Builder.SetInsertPoint(BB);
  
  // (10 + 20) * 2 の計算
  Value *Ten = Builder.getInt32(10);
  Value *Twenty = Builder.getInt32(20);
  Value *Two = Builder.getInt32(2);
  
  Value *Sum = Builder.CreateAdd(Ten, Twenty, "sum");
  Value *Result = Builder.CreateMul(Sum, Two, "result");
  
  Builder.CreateRet(Result);
  
  // 検証
  verifyFunction(*F, &errs());
  
  return M;
}

LLVMとデバッグ情報

デバッグ情報付きのIR生成

HLJSBASH

# デバッグ情報付きでコンパイル
clang -S -emit-llvm -g example.c -o example.ll

# 最適化してもデバッグ情報を保持
opt -O2 -S example.ll -o optimized.ll

DWARF情報の確認

HLJSBASH

# DWARF情報の表示
llvm-dwarfdump a.out

# デバッグセクションの確認
readelf --debug-dump=a.out

まとめ

LLVMは強力なコンパイラ基盤であり、言語開発者に豊富な最適化とコード生成機能を提供します。

LLVMを使うべき場面

新しい言語の開発: 言語フロントエンドを書けば、多数のターゲットに対応可能
静的解析ツール: IRベースの解析で高度なツールを開発
最適化研究: パスベースのアーキテクチャで新しい最適化を試せる
クロスコンパイル: 多数のアーキテクチャに対応

学習リソース

LLVM公式ドキュメント: https://llvm.org/docs/
LLVM Language Reference: https://llvm.org/docs/LangRef.html
Kaleidoscope チュートリアル: 言語実装のチュートリアル

次回はMLIRについて、より詳しく解説します。