Open2025/02/08にコメント追加28

LLVMで自作言語

自作言語的なものをLLVMで作りたい。
VMやスタックマシンを自分で定義して実装するよりも、JIT (Just In Time) コンパイルをさせたい。
なんなら最適化されたEXEファイルを吐いてくれるとうれしい。

自作言語のチュートリアルはいろいろある。低レイヤ寄りでいうとこのあたり。
「低レイヤを知りたい人のためのCコンパイラ作成入門」

爆速のリンカである lld の作者によるCコンパイラ入門。とても丁寧な内容で楽しい。

https://www.sigbus.info/compilerbook
「川合のプログラミング言語自作のためのテキスト」

名著・OS自作入門の著者によるテキスト。

http://essen.osask.jp/?a21_txt01
林晴比古『明快入門 コンパイラ・インタプリタ開発』

この本は紙で持っている。Cで字句解析やVMを実装する。中学生の頃にめっちゃ読んでた。

https://www.amazon.co.jp/dp/B00V7Y9MIO

Python の llvmlite というライブラリを使うと、わりと簡単に LLVM IR が吐けたりする。

ちなみに llvmlite は numba (PythonのJITコンパイルライブラリ) のプロジェクトで開発されているものらしい。あれもLLVMなんだなあ。

忘れていたが、昔からある LLVM 公式の Kaleidoscope 言語をつくるチュートリアルも一応ある。
ただ、ちょっと情報が古いらしいのと、説明が絶妙にわかりにくいところがある。（いきなりLexerの実装からはじめるんじゃないという気持ち）

https://llvm.org/docs/tutorial/

まずは準備体操として、もっとも単純なLLVMコードジェネレータを作ってみる。
なにもしない LLVM IR を吐くコード。

#include <stdio.h>

int main() {
  puts("define i32 @main() #0 {");
  puts("  ret i32 0");
  puts("}");
  return 0;
}

適当にコンパイルして c0.exe を作成しておく。c0 = compiler version 0。
これを使って LLVM IR を吐く。

c0.exe > output.ll

作成した output.llを clang に食わせる。
（この LLVM IR には、ターゲット環境を表す target triple を記載していない。勝手に補完したという旨の警告が出る）

clang -o output.exe output.ll

すると何もしない output.exe が生成される。

C言語の putchar 関数を呼んで「A」と表示させてみる。

#include <stdio.h>

int main() {
  // main の関数宣言
  printf("define i32 @main() #0 {\n");
  printf("  %%1 = call i32 @putchar(i32 %d)\n", 'A');
  printf("  ret i32 0\n");
  printf("}\n");

  // putchar の関数宣言
  printf("declare i32 @putchar(i32) #1\n");

  return 0;
}

どこからともなく putchar が出現しているが、clang はC言語のランライムライブラリとリンクしてくれるので問題ない。関数のプロトタイプを宣言しておくだけでよい。

先ほどと同様に、

c0.exe > output.ll
clang -o output.exe output.ll

の順に実行すると、コンソールに A と表示するEXEファイルができる。

立て続けに putchar を呼べば文字列が表示できる。

#include <stdio.h>

int main() {
  // main の関数宣言
  printf("define i32 @main() #0 {\n");
  // putchar(c) を繰り返し呼び出して hello world
  const char *str = "Hello, world!\n";
  for (int offset = 0; str[offset] != '\0'; offset++) {
    printf("  %%%d = call i32 @putchar(i32 %d)\n", offset + 1, str[offset]);
  }
  printf("  ret i32 0\n");
  printf("}\n");

  // putchar の関数宣言
  printf("declare i32 @putchar(i32) #1\n");

  return 0;
}

これで生成される LLVM IR はこんな感じ。

define i32 @main() #0 {
  %1 = call i32 @putchar(i32 72)
  %2 = call i32 @putchar(i32 101)
  %3 = call i32 @putchar(i32 108)
  %4 = call i32 @putchar(i32 108)
  %5 = call i32 @putchar(i32 111)
  %6 = call i32 @putchar(i32 44)
  %7 = call i32 @putchar(i32 32)
  %8 = call i32 @putchar(i32 119)
  %9 = call i32 @putchar(i32 111)
  %10 = call i32 @putchar(i32 114)
  %11 = call i32 @putchar(i32 108)
  %12 = call i32 @putchar(i32 100)
  %13 = call i32 @putchar(i32 33)
  %14 = call i32 @putchar(i32 10)
  ret i32 0
}
declare i32 @putchar(i32) #1

これをLLVMでコンパイルすると、ちゃんとハローワールドできる。

なんとなく LLVM を触る準備体操ができてきたので、そろそろ本当のLLVMライブラリを触ることにする。今回はCで書く。もっとモダンにやるならRustを使うのかもしれないけれど、細かいことを無視して雑に書ける言語を使いたい。

まずはLLVMのライブラリを導入する。
メイン開発機が Windows なので、ここでは vcpkg を使ってみる。

vcpkg install llvm

を実行すれば入る。
これでとりあえずOK……と思ったのだが、ビルドにめちゃくちゃ時間がかかってあまりお手軽じゃないし、ビルド結果が全部で80GBくらいになってストレージを逼迫してしまったので vcpkg を使う方法はやめることにした。

vcpkgでLLVMを導入するのは微妙だったので、素直にCMake+MSVCでビルドしてみる。

以下のサイトを参考にしてみる。
https://shining-corn.hatenablog.jp/entry/2020/10/31/142333
ここでは LLVM 19.1.0 を使う。
https://github.com/llvm/llvm-project/releases/tag/llvmorg-19.1.0
Releasesを眺めるといろいろダウンロードできるファイルがあるけれど、ここでは「llvm-project」からはじまるものを使う。他のファイルは一部分のソースコードしか入っていないので、単体だとCMakeが通らない。

llvm-project-19.1.0.src.tar.xz をダウンロードして、7-zipとかで適当に展開する。

cmake-gui で適当に Configure をする。上のリンクでは Optional toolset to use に「host=x64」と入れるべしと書かれていたのでそのようにした。

設定は、以下の項目にチェックを入れた。

LLVM_TOOL_CLANG_BUILD (clangをビルドする)

LLVM_TOOL_LLD_BUILD (lldをビルドする)

LLVM_TOOL_OPENMP_BUILD (OpenMPらしい。なんか面白そうなので追加)
これで Generate して Open Project を押す。あとは Visual Studio にビルドさせる。ここでは Debug ではなく MinSizeRel でビルドした。

ビルドは、長い時間がかかる＆CPU使用率が100%に張り付くので、待っている間はほかの遊びをする。

ビルドしていると途中で急にブルースクリーンで落ちるという謎現象に見舞われている。
4回くらいビルドを試してみたものの百発百中でダメだった。

原因はよくわからないけれど、ビルド中ずっとPCが操作できないくらい重くなるので、メモリ不足で倒れているのかも。16GB程度のマシンではダメなのか……？

LLVMの自炊ビルドはあきらめて、おとなしくReleaseページにあるWindowsビルドを使うことにする。
https://github.com/llvm/llvm-project/releases/tag/llvmorg-19.1.0
ここでは「clang+llvm-19.1.0-x86_64-pc-windows-msvc.tar.xz」を使う。このなかにLIBファイル、ヘッダファイルなどが一式そろっている。
Visual Studio 2019 のプロジェクトを作成して、適当な内容の main.cpp を作る。
#include <stdio.h>
#include <llvm/IR/LLVMContext.h>
#include <llvm/IR/Module.h>

int main()
{
    llvm::LLVMContext context;
    llvm::Module* mod = new llvm::Module(llvm::StringRef("MyModule"), context);

    printf("module name: %s\n", mod->getName().data());

    delete mod;
    return 0;
}
次に、ダウンロードしたLIBファイルやヘッダファイルを参照するように設定する。

設定する前に、プロパティページの上部にある 構成(C) を「すべての構成」、プラットフォーム(P) を「すべてのプラットフォーム」にしておく。

全般 > C++言語標準 : 「ISO C++20 標準」

C/C++ > 全般 > 追加のインクルードディレクトリ : 「(置いたパス)\clang+llvm-19.1.0-x86_64-pc-windows-msvc\include;%(AdditionalIncludeDirectories)」

C/C++ > 全般 > SDLチェック : 「いいえ」

C/C++ > コード生成 > ランタイムライブラリ : 「マルチスレッド (/MT)」

リンカー > 全般 > 追加のライブラリディレクトリ : 「(置いたパス)\clang+llvm-19.1.0-x86_64-pc-windows-msvc\lib;%(AdditionalLibraryDirectories)」

リンカー > 入力 > 追加の依存ファイル : 「ntdll.lib;LLVMAArch64AsmParser.lib;LLVMAArch64CodeGen.lib;LLVMAArch64Desc.lib;LLVMAArch64Disassembler.lib;LLVMAArch64Info.lib;LLVMAArch64Utils.lib;LLVMAggressiveInstCombine.lib;LLVMAnalysis.lib;LLVMARMAsmParser.lib;LLVMARMCodeGen.lib;LLVMARMDesc.lib;LLVMARMDisassembler.lib;LLVMARMInfo.lib;LLVMARMUtils.lib;LLVMAsmParser.lib;LLVMAsmPrinter.lib;LLVMBinaryFormat.lib;LLVMBitReader.lib;LLVMBitstreamReader.lib;LLVMBitWriter.lib;LLVMCFGuard.lib;LLVMCFIVerify.lib;LLVMCodeGen.lib;LLVMCodeGenData.lib;LLVMCodeGenTypes.lib;LLVMCore.lib;LLVMCoroutines.lib;LLVMCoverage.lib;LLVMDebugInfoBTF.lib;LLVMDebugInfoCodeView.lib;LLVMDebuginfod.lib;LLVMDebugInfoDWARF.lib;LLVMDebugInfoGSYM.lib;LLVMDebugInfoLogicalView.lib;LLVMDebugInfoMSF.lib;LLVMDebugInfoPDB.lib;LLVMDemangle.lib;LLVMDiff.lib;LLVMDlltoolDriver.lib;LLVMDWARFLinker.lib;LLVMDWARFLinkerClassic.lib;LLVMDWARFLinkerParallel.lib;LLVMDWP.lib;LLVMExecutionEngine.lib;LLVMExegesis.lib;LLVMExegesisAArch64.lib;LLVMExegesisX86.lib;LLVMExtensions.lib;LLVMFileCheck.lib;LLVMFrontendDriver.lib;LLVMFrontendHLSL.lib;LLVMFrontendOffloading.lib;LLVMFrontendOpenACC.lib;LLVMFrontendOpenMP.lib;LLVMFuzzerCLI.lib;LLVMFuzzMutate.lib;LLVMGlobalISel.lib;LLVMHipStdPar.lib;LLVMInstCombine.lib;LLVMInstrumentation.lib;LLVMInterfaceStub.lib;LLVMInterpreter.lib;LLVMipo.lib;LLVMIRPrinter.lib;LLVMIRReader.lib;LLVMJITLink.lib;LLVMLibDriver.lib;LLVMLineEditor.lib;LLVMLinker.lib;LLVMLTO.lib;LLVMMC.lib;LLVMMCA.lib;LLVMMCDisassembler.lib;LLVMMCJIT.lib;LLVMMCParser.lib;LLVMMIRParser.lib;LLVMObjCARCOpts.lib;LLVMObjCopy.lib;LLVMObject.lib;LLVMObjectYAML.lib;LLVMOptDriver.lib;LLVMOption.lib;LLVMOrcDebugging.lib;LLVMOrcJIT.lib;LLVMOrcShared.lib;LLVMOrcTargetProcess.lib;LLVMPasses.lib;LLVMProfileData.lib;LLVMRemarks.lib;LLVMRuntimeDyld.lib;LLVMSandboxIR.lib;LLVMScalarOpts.lib;LLVMSelectionDAG.lib;LLVMSupport.lib;LLVMSymbolize.lib;LLVMTableGen.lib;LLVMTableGenBasic.lib;LLVMTableGenCommon.lib;LLVMTarget.lib;LLVMTargetParser.lib;LLVMTextAPI.lib;LLVMTextAPIBinaryReader.lib;LLVMTransformUtils.lib;LLVMVectorize.lib;LLVMWindowsDriver.lib;LLVMWindowsManifest.lib;LLVMX86AsmParser.lib;LLVMX86CodeGen.lib;LLVMX86Desc.lib;LLVMX86Disassembler.lib;LLVMX86Info.lib;LLVMX86TargetMCA.lib;LLVMXRay.lib;%(AdditionalDependencies)」
ライブラリは "LLVM" から始まるファイルを一通りぶちこんである (C言語APIである LLVM-C.lib は除く)。あとは ntdll.lib も必要そうだったので追加した。
配布されているLIBファイルは Release x64 でビルドされているようなので、それに合わせた。（Debugでビルドすると「不一致が検出されました」と怒られる）
ビルドして実行するとすんなり動いた。配布されているLIBファイルはスタティックライブラリになっているらしく、追加のDLLは不要だった。

ようやくLLVMを呼び出せるようになったので、遊んでみようと思う。
Hello world するコードを生成してくれるサンプルを眺めながら実装してみる。
https://gist.github.com/snaka/1438344
ちなみにこのサンプルは古いLLVM向けに書かれているので、新しいLLVMで動かすには一部移植作業が必要になる。

まずはミニマルにやってみる。空っぽの LLVM IR を出力するコード。

#include <stdio.h>
#include <llvm/IR/LLVMContext.h>
#include <llvm/IR/Module.h>
#include <llvm/IR/Verifier.h>

int main()
{
    // LLVMコンテキストを作成
    llvm::LLVMContext context;

    // モジュールを作成
    // このモジュールに関数などを詰めこんでいって、コードを生成する
    // (今回は空っぽのモジュールとする)
    llvm::Module mod(llvm::StringRef("MyModule"), context);

    // モジュールを検証
    // 作ったモジュールが壊れていないかチェックする
    if (llvm::verifyModule(mod)) {
        printf("モジュールが壊れているので終了します\n");
        return 1;
    }

    // モジュールの LLVM IR を表示
    mod.print(llvm::outs(), nullptr);

    return 0;
}

実行すると、モジュール名だけが書かれた LLVM IR が標準出力に表示される。

; ModuleID = 'MyModule'
source_filename = "MyModule"

勉強になるリンクなど。

LLVM C++ API 学習メモ(1) - LLVM IRの生成と文字列形式での出力に倣って、なにもしないmain関数を生成してみる。
コードはリンク先とほぼ同じ。

#include <stdio.h>
#include <llvm/IR/LLVMContext.h>
#include <llvm/IR/Module.h>
#include <llvm/IR/Function.h>
#include <llvm/IR/BasicBlock.h>
#include <llvm/IR/IRBuilder.h>
#include <llvm/IR/Verifier.h>

int main()
{
    llvm::LLVMContext context;
    llvm::Module mod(llvm::StringRef("MyModule"), context);

    // main関数の型を用意
    llvm::FunctionType* funcMainType = llvm::FunctionType::get(
        llvm::Type::getInt32Ty(context),  // 返却値は int32
        false  // 可変長引数なし
    );

    // main関数を作成
    llvm::Function* funcMain = llvm::Function::Create(
        funcMainType,
        llvm::Function::ExternalLinkage,
        "main",
        mod
    );

    // BasicBlockを作成
    llvm::BasicBlock* mainBlock = llvm::BasicBlock::Create(context, "", funcMain);

    // BasicBlockに命令を追加
    llvm::IRBuilder<> builder(context);
    builder.SetInsertPoint(mainBlock);
    builder.CreateRet(builder.getInt32(0));  // ret i32 0

    llvm::verifyModule(mod);
    mod.print(llvm::outs(), nullptr);
    return 0;
}

実行すると return 0; をするだけのmain関数が書かれた LLVM IR が生成される。

; ModuleID = 'MyModule'
source_filename = "MyModule"

define i32 @main() {
  ret i32 0
}

これを clang につっこんでEXEファイルを吐かせてみる。

clang -o output.exe ir.ll

なにもしないEXEファイルができた。

ちょっと脇道に逸れるが、ポインタを解放していないのでメモリリークしそうなのが気になった。
llvm::Function* は、delete 演算子で消すとちゃんと親の Module から消えるらしい。

ここまででLLVMで何もしない関数ができた。

すぐにでも様々な機能（変数とか）を実装する旅に出発してもよいのだけれど、そのまえにLLVMの目玉ともいえるJITコンパイル機能を触ってみようと思う。
LLVMのJITコンパイラはいくつかあって、主に「MCJIT」というレガシーなものと、「ORC JIT」という新しいものがあるらしい。
MCJIT: llvm::ExecutionEngineクラスを使う
ORC: llvm::orc::LLJITクラスを使う
比較するとORCのほうが柔軟で、lazy compile (必要になったときだけ順次コンパイルする？) もできるらしい。たぶん新しく実装するならORCを使った方がよいのかも。
ORCの基本的な使い方は以下を眺めるのがよさそう。
https://llvm.org/docs/ORCv2.html

実際にJITコンパイルして実行するコードを書いてみる。
このあたりのサンプルが参考になった。

実装してみた。ここではモジュールの構築部分を関数に分けている。

#include <stdio.h>
#include <cstdint>
#include <memory>
#include <llvm/Support/TargetSelect.h>
#include <llvm/IR/LLVMContext.h>
#include <llvm/IR/Module.h>
#include <llvm/IR/Function.h>
#include <llvm/IR/BasicBlock.h>
#include <llvm/IR/IRBuilder.h>
#include <llvm/IR/Verifier.h>
#include <llvm/ExecutionEngine/Orc/LLJIT.h>
#include <llvm/ExecutionEngine/Orc/ThreadSafeModule.h>

llvm::orc::ThreadSafeModule createMyModule()
{
    // コンテキストとモジュールを作成
    // 注: LLJITにはスマートポインタで渡す必要があるので、
    // ここでは最初から unique_ptr で持っておくことにする。
    auto ctx = std::make_unique<llvm::LLVMContext>();
    auto mod = std::make_unique<llvm::Module>(llvm::StringRef("MyModule"), *ctx);

    // main関数を作成
    llvm::FunctionType* funcMainType = llvm::FunctionType::get(
        llvm::Type::getInt32Ty(*ctx),
        false
    );
    llvm::Function* funcMain = llvm::Function::Create(
        funcMainType,
        llvm::Function::ExternalLinkage,
        "main",
        *mod
    );
    llvm::BasicBlock* mainBlock = llvm::BasicBlock::Create(*ctx, "", funcMain);
    llvm::IRBuilder<> builder(*ctx);
    builder.SetInsertPoint(mainBlock);
    builder.CreateRet(builder.getInt32(12345));  // ret i32 12345

    // 検証＆画面表示
    llvm::verifyModule(*mod);
    mod->print(llvm::outs(), nullptr);
    puts("-----");

    return llvm::orc::ThreadSafeModule(std::move(mod), std::move(ctx));
}

int main()
{
    llvm::ExitOnError exitOnErr;

    // 初期化
    llvm::InitializeNativeTarget();  // ターゲットを設定 (e.g., x86_64-pc-windows)
    llvm::InitializeNativeTargetAsmPrinter();  // ターゲット向けAsmPrinterを設定

    // モジュールを作成
    auto tsm = createMyModule();

    // JITコンパイル
    auto jit = exitOnErr(llvm::orc::LLJITBuilder().create());
    jit->addIRModule(jit->getMainJITDylib(), std::move(tsm));

    // JITコンパイルされたmain関数を取得
    auto entrySymbol = exitOnErr(jit->lookup("main"));
    auto* mainFunction = entrySymbol.toPtr<std::int32_t(*)()>();

    // 実行
    std::int32_t retval = mainFunction();
    printf("返却値は %d です\n", retval);

    return 0;
}

ちなみにこの2行の初期化処理をあらかじめ実行しておかないと、LLVMがどの環境向けにコンパイルしたらいいか把握できないので、実行時にエラーが出てしまう。（ここでちょっとだけハマった）

    // 初期化
    llvm::InitializeNativeTarget();  // ターゲットを設定 (e.g., x86_64-pc-windows)
    llvm::InitializeNativeTargetAsmPrinter();  // ターゲット向けAsmPrinterを設定

実行すると、こんなふうに表示される。

; ModuleID = 'MyModule'
source_filename = "MyModule"

define i32 @main() {
  ret i32 12345
}
-----
返却値は 12345 です

今回の main 関数は 12345 という数値を返すようになっている。これがリアルタイムにコンパイル・実行された結果、実際に 12345 が返されているのがわかる。

ちゃんとJITコンパイルできてる。おもろい！

次に、JIT側から関数を呼び出してみる。

Hello world は簡単で、LLVM IR を直で出力したときと同じようにすればよい。
putchar関数を外部参照として定義して、1文字ずつ出力する。

#include <stdio.h>
#include <cstdint>
#include <memory>
#include <vector>
#include <llvm/Support/TargetSelect.h>
#include <llvm/IR/LLVMContext.h>
#include <llvm/IR/Module.h>
#include <llvm/IR/Function.h>
#include <llvm/IR/BasicBlock.h>
#include <llvm/IR/IRBuilder.h>
#include <llvm/IR/Verifier.h>
#include <llvm/ExecutionEngine/Orc/LLJIT.h>
#include <llvm/ExecutionEngine/Orc/ThreadSafeModule.h>

using namespace llvm;
using namespace llvm::orc;

ThreadSafeModule createMyModule()
{
    auto ctx = std::make_unique<LLVMContext>();
    auto mod = std::make_unique<Module>(StringRef("MyModule"), *ctx);
    IRBuilder<> builder(*ctx);

    // main関数を作成
    auto* funcMainType = FunctionType::get(builder.getInt32Ty(), false);
    auto* funcMain = Function::Create(funcMainType, Function::ExternalLinkage, "main", *mod);
    auto* mainBlock = BasicBlock::Create(*ctx, "", funcMain);

    // putchar関数を作成 (extern)
    std::vector<llvm::Type*> funcPutcharArgVec = { builder.getInt32Ty() };
    ArrayRef<Type*> funcPutcharArgs(funcPutcharArgVec);
    auto* funcPutcharType = llvm::FunctionType::get(builder.getInt32Ty(), funcPutcharArgs, false);
    auto funcPutchar = mod->getOrInsertFunction("putchar", funcPutcharType);

    // main関数の中身を作成
    builder.SetInsertPoint(mainBlock);
    builder.CreateCall(funcPutchar, builder.getInt32('H'));
    builder.CreateCall(funcPutchar, builder.getInt32('e'));
    builder.CreateCall(funcPutchar, builder.getInt32('l'));
    builder.CreateCall(funcPutchar, builder.getInt32('l'));
    builder.CreateCall(funcPutchar, builder.getInt32('o'));
    builder.CreateCall(funcPutchar, builder.getInt32(','));
    builder.CreateCall(funcPutchar, builder.getInt32(' '));
    builder.CreateCall(funcPutchar, builder.getInt32('w'));
    builder.CreateCall(funcPutchar, builder.getInt32('o'));
    builder.CreateCall(funcPutchar, builder.getInt32('r'));
    builder.CreateCall(funcPutchar, builder.getInt32('l'));
    builder.CreateCall(funcPutchar, builder.getInt32('d'));
    builder.CreateCall(funcPutchar, builder.getInt32('!'));
    builder.CreateCall(funcPutchar, builder.getInt32('\n'));
    builder.CreateRet(builder.getInt32(12345));  // ret i32 12345

    // 検証＆画面表示
    verifyModule(*mod);
    mod->print(outs(), nullptr);
    puts("-----");

    return ThreadSafeModule(std::move(mod), std::move(ctx));
}

int main()
{
    ExitOnError exitOnErr;
    InitializeNativeTarget();
    InitializeNativeTargetAsmPrinter();

    // モジュール作成
    auto tsm = createMyModule();

    // JITコンパイル
    auto jit = exitOnErr(LLJITBuilder().create());
    jit->addIRModule(jit->getMainJITDylib(), std::move(tsm));

    // 実行
    auto entrySymbol = exitOnErr(jit->lookup("main"));
    auto* mainFunction = entrySymbol.toPtr<std::int32_t(*)()>();
    std::int32_t retval = mainFunction();
    printf("返却値は %d です\n", retval);

    return 0;
}

実行結果:

; ModuleID = 'MyModule'
source_filename = "MyModule"

define i32 @main() {
  %1 = call i32 @putchar(i32 72)
  %2 = call i32 @putchar(i32 101)
  %3 = call i32 @putchar(i32 108)
  %4 = call i32 @putchar(i32 108)
  %5 = call i32 @putchar(i32 111)
  %6 = call i32 @putchar(i32 44)
  %7 = call i32 @putchar(i32 32)
  %8 = call i32 @putchar(i32 119)
  %9 = call i32 @putchar(i32 111)
  %10 = call i32 @putchar(i32 114)
  %11 = call i32 @putchar(i32 108)
  %12 = call i32 @putchar(i32 100)
  %13 = call i32 @putchar(i32 33)
  %14 = call i32 @putchar(i32 10)
  ret i32 12345
}

declare i32 @putchar(i32)
-----
Hello, world!
返却値は 12345 です

ちゃんと Hello world ができた。

ここでひとつ不思議なことが起きているのだがお気づきだろうか。コードを眺めてもらうとわかるかもしれないが、「putchar関数の実体はここにあるよ！」とは明示的に与えていないにもかかわらず、なぜputcharが呼べてしまっている。実は、JITコンパイラが自動的に参照先を探してくれているらしい。このケースでは、Cランタイムライブラリが呼ばれていると思われる。

このへんの話題は Kaleidscope のチュートリアルにも書いてあるのだけれど、何が起きているのかはいまいちピンとこない。なんかDLLのシンボル定義とかを自動的にサーチして見つけてくれる、というふんわりした認識でいる。これって環境によっては見つからなくてエラーになったりするのかな……？

ぜんぜんわからない、俺たちは雰囲気でJITをやっている。わからんけど便利なので、とりあえず次に進む。

今度は、C++側で自分で定義した関数を呼び出させてみる。

呼び出すと「やっほー」と出力する関数 void yahoo() をC++側で定義しておいて、それをJIT側で5回呼び出させたい。

独自関数の呼び出し方法も前述の Kaleidscope言語のチュートリアルに書かれていて、要するに DLLEXPORT を付けて関数を定義しておけば勝手に見つけてくれるらしい。

#include <stdio.h>
#include <cstdint>
#include <memory>
#include <vector>
#include <llvm/Support/TargetSelect.h>
#include <llvm/IR/LLVMContext.h>
#include <llvm/IR/Module.h>
#include <llvm/IR/Function.h>
#include <llvm/IR/BasicBlock.h>
#include <llvm/IR/IRBuilder.h>
#include <llvm/IR/Verifier.h>
#include <llvm/ExecutionEngine/Orc/LLJIT.h>
#include <llvm/ExecutionEngine/Orc/ThreadSafeModule.h>

using namespace llvm;
using namespace llvm::orc;

#ifdef _WIN32
#define DLLEXPORT __declspec(dllexport)
#else
#define DLLEXPORT
#endif

// JIT側から呼び出したい関数: yahoo()
extern "C" DLLEXPORT void yahoo() {
    puts("やっほー");
}

ThreadSafeModule createMyModule()
{
    auto ctx = std::make_unique<LLVMContext>();
    auto mod = std::make_unique<Module>(StringRef("MyModule"), *ctx);
    IRBuilder<> builder(*ctx);

    // main関数を作成
    auto* funcMainType = FunctionType::get(builder.getInt32Ty(), false);
    auto* funcMain = Function::Create(funcMainType, Function::ExternalLinkage, "main", *mod);
    auto* mainBlock = BasicBlock::Create(*ctx, "", funcMain);

    // yahoo関数を作成 (extern)
    auto* funcYahooType = llvm::FunctionType::get(builder.getVoidTy(), false);
    auto funcYahoo = mod->getOrInsertFunction("yahoo", funcYahooType);

    // main関数の中身を作成
    builder.SetInsertPoint(mainBlock);
    builder.CreateCall(funcYahoo);  // 関数 yahoo を呼び出す
    builder.CreateCall(funcYahoo);  // 関数 yahoo を呼び出す
    builder.CreateCall(funcYahoo);  // 関数 yahoo を呼び出す
    builder.CreateCall(funcYahoo);  // 関数 yahoo を呼び出す
    builder.CreateCall(funcYahoo);  // 関数 yahoo を呼び出す
    builder.CreateRet(builder.getInt32(12345));  // ret i32 12345

    // 検証＆画面表示
    verifyModule(*mod);
    mod->print(outs(), nullptr);
    puts("-----");

    return ThreadSafeModule(std::move(mod), std::move(ctx));
}

int main()
{
    ExitOnError exitOnErr;
    InitializeNativeTarget();
    InitializeNativeTargetAsmPrinter();

    // モジュール作成
    auto tsm = createMyModule();

    // JITコンパイル
    auto jit = exitOnErr(LLJITBuilder().create());
    jit->addIRModule(jit->getMainJITDylib(), std::move(tsm));

    // 実行
    auto entrySymbol = exitOnErr(jit->lookup("main"));
    auto* mainFunction = entrySymbol.toPtr<std::int32_t(*)()>();
    std::int32_t retval = mainFunction();
    printf("返却値は %d です\n", retval);

    return 0;
}

実行結果:

; ModuleID = 'MyModule'
source_filename = "MyModule"

define i32 @main() {
  call void @yahoo()
  call void @yahoo()
  call void @yahoo()
  call void @yahoo()
  call void @yahoo()
  ret i32 12345
}

declare void @yahoo()
-----
やっほー
やっほー
やっほー
やっほー
やっほー
返却値は 12345 です

いとも簡単にできてしまった。素晴らしい。

昔、Lua組み込みアプリケーションでC言語側で定義した関数を呼び出すときに、頑張って処理系に関数ポインタを渡したりしていたような記憶がある。それと比べればこんなに簡単にシンボルを見つけてくれるのはすごいことだなあと思う。

ちなみに DLLEXPORT を外すと、関数の参照に失敗して Symbols not found というエラーを吐く。

// JIT側から呼び出したい関数: yahoo()
extern "C" /*DLLEXPORT*/ void yahoo() {
    puts("やっほー");
}

; ModuleID = 'MyModule'
source_filename = "MyModule"

define i32 @main() {
  call void @yahoo()
  call void @yahoo()
  call void @yahoo()
  call void @yahoo()
  call void @yahoo()
  ret i32 12345
}

declare void @yahoo()
-----
JIT session error: Symbols not found: [ yahoo ]
Failed to materialize symbols: { (main, { main }) }

実際に自作言語を作るときは、言語仕様によってはシステム側の関数を呼び出せてしまうことになるので、変なハックができてしまいそう。避けたい場合は、関数名を適当にマングリングしておいたほうがよいかも（たとえば関数名の最初に言語名+アンダーバーを入れておくとか）。

以上で、JITコンパイル機能で必要になるところはひとまず使ってみることができた。

今度はコード最適化をやってみる。やっぱりLLVMといえば高度な最適化ができるところ。
コード最適化は Optimization Pass という機能として提供されている。

使い方は Kaleidoscope のサンプルを見るのが手っ取り早い。
https://llvm.org/docs/tutorial/MyFirstLanguageFrontend/LangImpl04.html#llvm-optimization-passes
もうちょっとちゃんとした使い方は、以下の公式ドキュメントを見るとよさそう。
https://llvm.org/docs/NewPassManager.html

まずは簡単な最適化を試したいので、「1+2=3」を計算させてみる。

単純な加算

main関数の作成部を以下のように書き換えればよい。加算命令は builder.CreateAdd() で作成できる。

// main関数の中身を作成
builder.SetInsertPoint(mainBlock);
builder.CreateRet(
    builder.CreateAdd(builder.getInt32(1), builder.getInt32(2))
);  // return 1 + 2

実はこの書き方をすると、最適化パスをかけるまでもなく自動的に定数展開をしてくれる。生成された LLVM IR を見てみると、加算命令は跡形もなく消えているのがわかる。

; ModuleID = 'MyModule'
source_filename = "MyModule"

define i32 @main() {
  ret i32 3
}

この仕様は実用上うれしいのだけれど、これでは最適化の実験ができない。

そこで、いったんローカル変数に代入することであえて効率の悪いコードを生成させる。疑似コードで書けばこんなイメージ。

a = 1
b = 2
c = 1 + 2
return c

ここから最適化をかけた結果として、return だけが残ってくれれば成功。

return 3

では、ローカル変数の作り方を見ていく。

確保

ローカル変数をLLVM上に確保するには builder.CreateAlloca() を使う。

auto* varA = builder.CreateAlloca(builder.getInt32Ty());  // var a: i32

ちなみに varA は、ローカル変数のメモリアドレスを保持している。たとえばこれ自体を return するとポインタを返していることになってしまうので注意。値が欲しいときは後述の builder.CreateLoad() を使う。

builder.CreateRet(varA);  // return &a

代入

代入命令を作るには builder.CreateStore() を使う。

builder.CreateStore(builder.getInt32(1), varA);  // a = 1

取得

取得命令を作るには builder.CreateLoad() を使う。ちなみに新しいLLVM (14以降?) で引数が変更されていて、変数の型を指定する必要がある。

auto* value = builder.CreateLoad(builder.getInt32Ty(), varA);
builder.CreateRet(value);  // return a

以下は古いLLVMでの書き方。

auto* value = builder.CreateLoad(varA);
builder.CreateRet(value);  // return a

ローカル変数版 1+2=3

つまり、以下のように書くとローカル変数を使った冗長な 1+2=3 ができる。

// main関数の中身を作成
builder.SetInsertPoint(mainBlock);
auto* varA = builder.CreateAlloca(builder.getInt32Ty(), nullptr, "a");  // var a: i32
auto* varB = builder.CreateAlloca(builder.getInt32Ty(), nullptr, "b");  // var b: i32
auto* varC = builder.CreateAlloca(builder.getInt32Ty(), nullptr, "c");  // var c: i32
builder.CreateStore(builder.getInt32(1), varA);  // a = 1
builder.CreateStore(builder.getInt32(2), varB);  // b = 1
auto* valueC = builder.CreateAdd(
    builder.CreateLoad(builder.getInt32Ty(), varA),
    builder.CreateLoad(builder.getInt32Ty(), varB)
);
builder.CreateStore(valueC, varC);  // c = a + b
builder.CreateRet(builder.CreateLoad(builder.getInt32Ty(), varC));  // return c

生成された LLVM IR はこんな感じ。まだ最適化されていないので、大したことはしていないのに長い。

; ModuleID = 'MyModule'
source_filename = "MyModule"

define i32 @main() {
  %a = alloca i32, align 4
  %b = alloca i32, align 4
  %c = alloca i32, align 4
  store i32 1, ptr %a, align 4
  store i32 2, ptr %b, align 4
  %1 = load i32, ptr %b, align 4
  %2 = load i32, ptr %a, align 4
  %3 = add i32 %2, %1
  store i32 %3, ptr %c, align 4
  %4 = load i32, ptr %c, align 4
  ret i32 %4
}

ここからが本番。コード最適化の機能を呼び出してみる。

公式ドキュメントの Using New Pass Manager を参考に llvm::ModulePathManager を組み立てる。GCC の -O2 みたいな指定ができるっぽい。独自の Pass を定義してより高度な最適化をすることもできるっぽい。

// 最適化の準備
auto lam = std::make_unique<LoopAnalysisManager>();
auto fam = std::make_unique<FunctionAnalysisManager>();
auto cgam = std::make_unique<CGSCCAnalysisManager>();
auto mam = std::make_unique<ModuleAnalysisManager>();
auto pb = std::make_unique<PassBuilder>();
pb->registerLoopAnalyses(*lam);
pb->registerFunctionAnalyses(*fam);
pb->registerCGSCCAnalyses(*cgam);
pb->registerModuleAnalyses(*mam);
pb->crossRegisterProxies(*lam, *fam, *cgam, *mam);
auto mpm = pb->buildPerModuleDefaultPipeline(OptimizationLevel::O2);

作成した ModulePathManager を実行する。実行のタイミングはモジュールの verify 後あたりがよいと思われる。

// 検証＆最適化
verifyModule(*mod);
mpm.run(*mod, *mam);

ソースコード全体

#include <stdio.h>
#include <cstdint>
#include <memory>
#include <vector>
#include <llvm/Support/TargetSelect.h>
#include <llvm/IR/LLVMContext.h>
#include <llvm/IR/Module.h>
#include <llvm/IR/Function.h>
#include <llvm/IR/BasicBlock.h>
#include <llvm/IR/IRBuilder.h>
#include <llvm/IR/Verifier.h>
#include <llvm/IR/PassManager.h>
#include <llvm/Passes/PassBuilder.h>
#include <llvm/Transforms/Scalar/InstSimplifyPass.h>
#include <llvm/ExecutionEngine/Orc/LLJIT.h>
#include <llvm/ExecutionEngine/Orc/ThreadSafeModule.h>

using namespace llvm;
using namespace llvm::orc;

ThreadSafeModule createModule()
{
    auto ctx = std::make_unique<LLVMContext>();
    auto mod = std::make_unique<Module>(StringRef("MyModule"), *ctx);
    IRBuilder<> builder(*ctx);

    // 最適化の準備
    auto lam = std::make_unique<LoopAnalysisManager>();
    auto fam = std::make_unique<FunctionAnalysisManager>();
    auto cgam = std::make_unique<CGSCCAnalysisManager>();
    auto mam = std::make_unique<ModuleAnalysisManager>();
    auto pb = std::make_unique<PassBuilder>();
    pb->registerLoopAnalyses(*lam);
    pb->registerFunctionAnalyses(*fam);
    pb->registerCGSCCAnalyses(*cgam);
    pb->registerModuleAnalyses(*mam);
    pb->crossRegisterProxies(*lam, *fam, *cgam, *mam);
    auto mpm = pb->buildPerModuleDefaultPipeline(OptimizationLevel::O2);

    // putchar関数を作成 (extern)
    std::vector<llvm::Type*> funcPutcharArgVec = { builder.getInt32Ty() };
    ArrayRef<Type*> funcPutcharArgs(funcPutcharArgVec);
    auto* funcPutcharType = llvm::FunctionType::get(builder.getInt32Ty(), funcPutcharArgs, false);
    auto funcPutchar = mod->getOrInsertFunction("putchar", funcPutcharType);

    // main関数を作成
    auto* funcMainType = FunctionType::get(builder.getInt32Ty(), false);
    auto* funcMain = Function::Create(funcMainType, Function::ExternalLinkage, "main", *mod);
    auto* mainBlock = BasicBlock::Create(*ctx, "", funcMain);

    // main関数の中身を作成
    builder.SetInsertPoint(mainBlock);
    auto* varA = builder.CreateAlloca(builder.getInt32Ty(), nullptr, "a");  // var a: i32
    auto* varB = builder.CreateAlloca(builder.getInt32Ty(), nullptr, "b");  // var b: i32
    auto* varC = builder.CreateAlloca(builder.getInt32Ty(), nullptr, "c");  // var c: i32
    builder.CreateStore(builder.getInt32(1), varA);  // a = 1
    builder.CreateStore(builder.getInt32(2), varB);  // b = 1
    auto* valueC = builder.CreateAdd(
        builder.CreateLoad(builder.getInt32Ty(), varA),
        builder.CreateLoad(builder.getInt32Ty(), varB)
    );
    builder.CreateStore(valueC, varC);  // c = a + b
    builder.CreateRet(builder.CreateLoad(builder.getInt32Ty(), varC));  // return c

    // 検証＆最適化
    verifyModule(*mod);
    mpm.run(*mod, *mam);

    // 生成された LLVM IR を表示
    mod->print(outs(), nullptr);
    puts("-----");

    return ThreadSafeModule(std::move(mod), std::move(ctx));
}

void runModule(ThreadSafeModule tsm)
{
    ExitOnError exitOnErr;
    InitializeNativeTarget();
    InitializeNativeTargetAsmPrinter();

    // JITコンパイル
    auto jit = exitOnErr(LLJITBuilder().create());
    jit->addIRModule(jit->getMainJITDylib(), std::move(tsm));

    // 実行
    auto symbol = exitOnErr(jit->lookup("main"));
    auto* mainFunction = symbol.toPtr<std::int32_t(*)()>();
    std::int32_t retval = mainFunction();
    printf("-> %d\n", retval);
}

int main()
{
    auto tsm = createModule();
    runModule(std::move(tsm));
    return 0;
}

この最適化パスを適用して生成された LLVM IR が以下のとおり。

; ModuleID = 'MyModule'
source_filename = "MyModule"

; Function Attrs: mustprogress nofree norecurse nosync nounwind willreturn memory(none)
define noundef i32 @main() local_unnamed_addr #0 {
  ret i32 3
}

attributes #0 = { mustprogress nofree norecurse nosync nounwind willreturn memory(none) }

すごい。不要な中間変数や演算がちゃんと削除されて、return 3 だけになっている！

ここまでをざっと振り返ってみる。だいたいピースが揃った。
JITコンパイル＆実行
コード最適化
関数定義
外部関数の呼び出し
ローカル変数
四則演算
あとやれていないのは、条件分岐とループくらいかも。

以上の内容にくわえて適当にパーサとコードジェネレータを実装してしまえば、トイ言語が作れそう。

「プログラミング言語の作り方」
こういうサイトもあるらしい。
https://3iz.jp/

自作言語を作るにあたって、よくある処理系の処理手順をおさらいしてみる。

字句解析：自作言語で書かれたプログラムをトークン（単語のようなもの）へ分割する

構文解析：トークンの並びから抽象構文木（文や式の構造を表した木構造）を作る

コード生成：抽象構文木をたどりながらマシンコードやバイトコードを生成する
この3つに分かれることが多いが、もっと簡略化して実装する場合もある（たとえば字句解析と構文解析を同時におこなう、構文解析とコード生成を同時におこなうなど）。
字句解析 (lexical analysis) をおこなうプログラムを レキサ (lexer) と呼ぶ。

構文解析 (parsing) をおこなうプログラムを パーサ (parser) と呼ぶ。

字句解析・構文解析をおこなうプログラムをまとめて（広義の）パーサとも呼ぶ。
レキサやパーサを実装するにあたって、普通にC++等で手書きしてもよいのだけれど、パーサジェネレータ（コンパイラコンパイラ）と呼ばれるソフトを使うことでレキサやパーサのソースコードを自動生成することもできる。
パーサジェネレータとして yacc/lex がある。あらかじめ構文のルールを定義したファイルを用意しておくと、lex はレキサのC言語コードを生成し、yacc はパーサのC言語コードを生成してくれる。

もとは1970年代にUNIX向けに作られたものだそうで歴史が深い。現在はオリジナルの yacc/lex が使われることはほとんどなく、GNUプロジェクトの一部である Bison/Flex が使われることが多いようす。（Bison は「ヤク」に対して「バイソン」というGNUならではの偶蹄類ジョーク？）
yacc系は非常に古めかしいソフトウェアなので、ほかのパーサジェネレータも挙げてみる。

ANTLR (アントラー) : サンフランシスコ大教授→Googleの人が開発しているソフトウェア。わりと昔からあるが現在も開発が続いている。ツール類が豊富に整っているっぽい。よくあるLR法ではなくLL(*)法を使う。

Boost::Spirit : Boostはなんでも揃っているライブラリだが、なんと構文解析器もあるらしい。パーサジェネレータというよりは手書き寄りだけれど便利らしい。

CTPG : Compile Time Parser Generator の略で、その名の通りC++のコンパイル時にパーサを生成してくれる超絶技巧の産物。

Ragel : ステートマシンを使ったパーサジェネレータ。最近はあまり活発に開発されていなさそう。

忘れてたけど Crafting Interpreter という本もある。
インプレスから邦訳本も出ている。