LLVM APIを使ってみよう！ 〜 Brainf**kコンパイラをIRBuilderで書き直してみた 〜

先日LLVMの入門記事を書きました。 clangが吐くLLVM IR (Intermediate representation, 中間表現) を頼りに、Brainf**kのコンパイラを書いてみました。 itchyny.hatenablog.com この記事で書いたコードでは、直接printfでLLVM IRの命令を出力していました。 このステップを踏むことで、LLVM IRの命令をどう調べればいいかについて身についたと思います。

しかし、この「コンパイラ」は次のような問題がありました。

• bf2llvmコマンドが出力するのがLLVM IRのために、lliã‚„llcといったLLVM IRのランタイムやコンパイラが必要となる
• 最適化を行うにはさらにoptコマンドが必要になり、やはりLLVMツールチェインをインストールしている環境でしか使えない
• ソースコードから実行ファイルまでのパスの中で、LLVM IRの文字列に変換してパースしている箇所がある
• 不正なIRコードを吐く可能性も高い
• 一時変数のインデックスを自前で管理しており、メンテナンス性も悪い

LLVMツールチェインには、LLVM IRのコードをプログラムから吐くためのAPIも含まれています。 今回はLLVM APIを使ってコンパイラを作る練習をしてみます。

LLVM API, Hello world!

まずはとても短いコードを生成するところから始めましょう。 Kaleidoscopeのチュートリアルを横目にしながらコードを書いていきます。

次のようなコードを考えてみます。

test.c

int main() {
  return 42;
}

このコードに対応するLLVM IRのコードは次のようになります (clang -S -emit-llvm -O2 test.cの出力を削ったものです)。

test.ll

define i32 @main() {
  ret i32 42
}

このIRを吐くコードを書いてみます。

test.cpp

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

static llvm::LLVMContext TheContext;
static llvm::IRBuilder<> Builder(TheContext);
static std::unique_ptr<llvm::Module> TheModule;

int main() {
  TheModule = llvm::make_unique<llvm::Module>("top", TheContext);
  llvm::Function* mainFunc = llvm::Function::Create(
      llvm::FunctionType::get(llvm::Type::getInt32Ty(TheContext), false),
      llvm::Function::ExternalLinkage, "main", TheModule.get());
  Builder.SetInsertPoint(llvm::BasicBlock::Create(TheContext, "", mainFunc));

  Builder.CreateRet(Builder.getInt32(42));

  TheModule->dump();
}

コンパイルして実行してみます。

 $ g++ `llvm-config --cxxflags --ldflags --libs --system-libs` test.cpp -o test
 $ ./test
; ModuleID = 'top'
source_filename = "top"

define i32 @main() {
  ret i32 42
}
 $ ./test 2>&1 | lli
 $ echo $?
42

TheModule->dump()が標準エラー出力にIRを出力するので2>&1しています。 lliを使うとLLVM IR命令列を直接実行して、動作を確認することができます。

簡単なところから説明していきましょう。 次の行はret i32 42を生成しているコードです。

  Builder.CreateRet(Builder.getInt32(42));

IRBuilderの各種メソッドを調べる時は、doxygenで生成されたヘルプが役に立ちます。 CreateRetの引数は1つで、Value*を取ります。 getInt32はIRBuilderBaseで定義されています。

次のコードはdefine i32 @main()に対応します。

  llvm::Function* mainFunc = llvm::Function::Create(
      llvm::FunctionType::get(llvm::Type::getInt32Ty(TheContext), false),
      llvm::Function::ExternalLinkage, "main", TheModule.get());

llvm::FunctionType::getでググって出て来るFunctionTypeを見ると、llvm::FunctionType::getの引数は2つまたは3つで、引数の型は省略できることがわかります。 関数を作った後に中身を生成するには、SetInsertPointを使ってコードを吐く場所を指定します。

  Builder.SetInsertPoint(llvm::BasicBlock::Create(TheContext, "", mainFunc));

llvm::BasicBlock::Createはコードブロックを作り、ラベルを生成します。

  Builder.SetInsertPoint(llvm::BasicBlock::Create(TheContext, "entry", mainFunc));

このようにラベル名を指定すると、次のようになります。

define i32 @main() {
entry:
  ret i32 42
}

ラベルを使って遊んでみましょう。 br (branch) 命令を使って作ったラベルにジャンプしてみます。

test.c

  Builder.SetInsertPoint(llvm::BasicBlock::Create(TheContext, "entry", mainFunc));
  llvm::BasicBlock* newBlock = llvm::BasicBlock::Create(TheContext, "new_label", mainFunc);
  Builder.CreateBr(newBlock);

  Builder.CreateRet(Builder.getInt32(42));

  Builder.SetInsertPoint(newBlock);
  Builder.CreateRet(Builder.getInt32(36));

動作を確認します。

 $ g++ `llvm-config --cxxflags --ldflags --libs --system-libs` test.cpp -o test
 $ ./test
; ModuleID = 'top'
source_filename = "top"

define i32 @main() {
entry:
  br label %new_label
  ret i32 42

new_label:                                        ; preds = %entry
  ret i32 36
}
 $ ./test 2>&1 | lli
 $ echo $?
36

llvm::BasicBlock::Create→Builder.CreateBrの順に呼んでいますが、きちんと下のラベルへのbr命令を作ることができています。 llvm::BasicBlock::Createは、指定された関数の一番最後にブロックを生成するという関数なのです (第四引数を指定して生成場所を制御することもできます)。

次に、簡単な演算を行うコードを生成してみます。

int main() {
  int a, b;
  a = 32;
  b = a + 8;
  return a + b;
}

72で終了するコードです。 これに対応するLLVM IRコードを手で書いてみます。 IRに慣れてきて、これくらいのサイズなら手で書けるようになってきました。

test.ll

define i32 @main() {
  %a = alloca i32
  %b = alloca i32
  store i32 32, i32* %a
  %1 = load i32, i32* %a
  %2 = add i32 %1, 8
  store i32 %2, i32* %b
  %3 = load i32, i32* %a
  %4 = load i32, i32* %b
  %5 = add i32 %3, %4
  ret i32 %5
}

実際このコードは実行できます。

 $ lli test.ll
 $ echo $?
72

このLLVM IRを出力するコードをIRBuilderを使って書いてみます。

test.cpp

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

static llvm::LLVMContext TheContext;
static llvm::IRBuilder<> Builder(TheContext);
static std::unique_ptr<llvm::Module> TheModule;

int main() {
  TheModule = llvm::make_unique<llvm::Module>("top", TheContext);
  llvm::Function* mainFunc = llvm::Function::Create(
      llvm::FunctionType::get(llvm::Type::getInt32Ty(TheContext), false),
      llvm::Function::ExternalLinkage, "main", TheModule.get());
  Builder.SetInsertPoint(llvm::BasicBlock::Create(TheContext, "", mainFunc));

  llvm::Value* a = Builder.CreateAlloca(Builder.getInt32Ty(), nullptr, "a");
  llvm::Value* b = Builder.CreateAlloca(Builder.getInt32Ty(), nullptr, "b");
  Builder.CreateStore(Builder.getInt32(32), a);
  Builder.CreateStore(Builder.CreateAdd(Builder.CreateLoad(a), Builder.getInt32(8)), b);

  Builder.CreateRet(Builder.CreateAdd(Builder.CreateLoad(a), Builder.CreateLoad(b)));

  TheModule->dump();
}

動作を確認します。

 $ g++ `llvm-config --cxxflags --ldflags --libs --system-libs` test.cpp -o test
 $ ./test
; ModuleID = 'top'
source_filename = "top"

define i32 @main() {
  %a = alloca i32
  %b = alloca i32
  store i32 32, i32* %a
  %1 = load i32, i32* %a
  %2 = add i32 %1, 8
  store i32 %2, i32* %b
  %3 = load i32, i32* %a
  %4 = load i32, i32* %b
  %5 = add i32 %3, %4
  ret i32 %5
}
 $ ./test 2>&1 | lli
72

少しずつIRBuilderの触り方が分かってきました。 LLVM IRのどの命令を使えばいいかわかっていれば、IRBuilderのドキュメントの中でページ内検索してコードを書いていくことができます。

  Builder.CreateStore(Builder.CreateAdd(Builder.CreateLoad(a), Builder.getInt32(8)), b);

この一行が次の三行に対応することがわかります。

  %1 = load i32, i32* %a
  %2 = add i32 %1, 8
  store i32 %2, i32* %b

これならわざわざ一時変数のためのインデックスを自前で管理しなくても良いですね。 だいぶコードを書くのが楽になりますね。

きつねさんでもわかるLLVM ~コンパイラを自作するためのガイドブック~

Brainf**kのコンパイラを書いてみよう！

前回の記事でもBrainf**kのコンパイラを書きましたが、直接LLVM IRを吐くコードだったために一時変数を管理しないといけない、不正なコードを出力してしまいそうになる、ソースコードがダサいと言った問題がありました。 今回はLLVM APIを使って書き直してみましょう。

まずはBrainf**kのデータ領域の確保と開放を行う部分を書いてみます。 Cで書くと

#include <stdlib.h>

int main() {
  char* data = (char*)calloc(30000, sizeof(char));
  char* ptr = data;
  free(data);
}

に対応するコードです。

bf2llvm.cpp

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

static llvm::LLVMContext TheContext;
static llvm::IRBuilder<> Builder(TheContext);
static std::unique_ptr<llvm::Module> TheModule;

int main() {
  TheModule = llvm::make_unique<llvm::Module>("top", TheContext);
  llvm::Function* mainFunc = llvm::Function::Create(
      llvm::FunctionType::get(llvm::Type::getInt32Ty(TheContext), false),
      llvm::Function::ExternalLinkage, "main", TheModule.get());
  Builder.SetInsertPoint(llvm::BasicBlock::Create(TheContext, "", mainFunc));

  llvm::Value* data = Builder.CreateAlloca(Builder.getInt8PtrTy(), nullptr, "data");
  llvm::Value* ptr = Builder.CreateAlloca(Builder.getInt8PtrTy(), nullptr, "ptr");
  llvm::Function* funcCalloc = llvm::cast<llvm::Function>(
      TheModule->getOrInsertFunction("calloc",
        Builder.getInt8PtrTy(),
        Builder.getInt64Ty(), Builder.getInt64Ty(),
        nullptr));
  llvm::Value* data_ptr = Builder.CreateCall(funcCalloc, {Builder.getInt64(30000), Builder.getInt64(1)});
  Builder.CreateStore(data_ptr, data);
  Builder.CreateStore(data_ptr, ptr);

  llvm::Function* funcFree = llvm::cast<llvm::Function>(
      TheModule->getOrInsertFunction("free",
        Builder.getVoidTy(),
        Builder.getInt8PtrTy(),
        nullptr));
  Builder.CreateCall(funcFree, {Builder.CreateLoad(data)});

  Builder.CreateRet(Builder.getInt32(0));

  TheModule->dump();
}

実行して動作を確かめます。

 $ g++ `llvm-config --cxxflags --ldflags --libs --system-libs` bf2llvm.cpp -o bf2llvm
 $ ./bf2llvm
; ModuleID = 'top'
source_filename = "top"

define i32 @main() {
  %data = alloca i8*
  %ptr = alloca i8*
  %1 = call i8* @calloc(i64 30000, i64 1)
  store i8* %1, i8** %data
  store i8* %1, i8** %ptr
  %2 = load i8*, i8** %data
  call void @free(i8* %2)
  ret i32 0
}

declare i8* @calloc(i64, i64)

declare void @free(i8*)

関数callocとfreeを呼んでいますね。

  llvm::Function* funcCalloc = llvm::cast<llvm::Function>(
      TheModule->getOrInsertFunction("calloc",
        Builder.getInt8PtrTy(),
        Builder.getInt64Ty(), Builder.getInt64Ty(),
        nullptr));
  llvm::Value* data_ptr = Builder.CreateCall(funcCalloc, {Builder.getInt64(30000), Builder.getInt64(1)});

getOrInsertFunctionでは関数名、返り値の型と引数の型を取ります。 モジュールの中から関数を探して返しますが、もしなければdeclareによって宣言します (リンク時に解決されます)。 そしてCreateCallによってcall命令を作っています。

次はポインタの移動を書いてみます。 Brainf**kでは>, <命令に相当するコードです。 Cだと++ptr, --ptrに対応します。 前回のエントリーでは次のように書いていました。

int idx = 1;
void emit_move_ptr(int diff) {
  printf("  %%%d = load i8*, i8** %%ptr, align 8\n", idx);
  printf("  %%%d = getelementptr inbounds i8, i8* %%%d, i32 %d\n", idx + 1, idx, diff);
  printf("  store i8* %%%d, i8** %%ptr, align 8\n", idx + 1);
  idx += 2;
}

これは次のようになります。

void emit_move_ptr(llvm::Value* ptr, int diff) {
  Builder.CreateStore(
      Builder.CreateInBoundsGEP(
        Builder.getInt8Ty(),
        Builder.CreateLoad(ptr),
        Builder.getInt32(diff)),
      ptr);
}

CreateInBoundsGEPがgetelementptr命令を生成します。

次に、メモリーに足したり引いたりする+, -命令に相当するコードを書いてみます。 Cで書くと++*ptrã‚„--*ptrとなるコードですね。

void emit_add(llvm::Value* ptr, int diff) {
  llvm::Value* tmp = Builder.CreateLoad(ptr);
  Builder.CreateStore(
      Builder.CreateAdd(
        Builder.CreateLoad(tmp),
        Builder.getInt8(diff)),
      tmp);
}

そして、Brainf**kの., Cではputchar(*ptr)に相当するコードを書いてみます。 前回見たように、sext命令でi8からi32に変換する必要があります。

void emit_put(llvm::Value* ptr) {
  llvm::Function* funcPutChar = llvm::cast<llvm::Function>(
      TheModule->getOrInsertFunction("putchar",
        Builder.getInt32Ty(),
        Builder.getInt32Ty(),
        nullptr));
  Builder.CreateCall(
      funcPutChar,
      Builder.CreateSExt(
        Builder.CreateLoad(Builder.CreateLoad(ptr)),
        Builder.getInt32Ty()));
}

これで>, <, +, -, .の5命令の準備ができたので、標準入力からBrainf**kを受け取ってLLVM IRを吐くようにしてみましょう。

bf2llvm.cpp

// ...
  llvm::Value* data_ptr = Builder.CreateCall(funcCalloc, {Builder.getInt64(30000), Builder.getInt64(1)});
  Builder.CreateStore(data_ptr, data);
  Builder.CreateStore(data_ptr, ptr);

  char c;
  while (std::cin.get(c)) {
    switch (c) {
      case '>': emit_move_ptr(ptr, 1); break;
      case '<': emit_move_ptr(ptr, -1); break;
      case '+': emit_add(ptr, 1); break;
      case '-': emit_add(ptr, -1); break;
      case '.': emit_put(ptr); break;
    }
  }

  llvm::Function* funcFree = llvm::cast<llvm::Function>(
// ...

動かしてみましょう。

 $ g++ `llvm-config --cxxflags --ldflags --libs --system-libs` bf2llvm.cpp -o bf2llvm
 $ echo "++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.+++++++++++++++++++++++++++++.+++++++..+++.>++++++++++++++++++++++++++++++++.<++++++++.--------.+++.------.--------.>+." | ./bf2llvm 2>&1 | lli
Hello world!

正しくIRを吐けてるようですね。

ループに対応しよう

Brainf**kの[はC言語のwhile (*ptr) {に、]は}に対応します。 LLVM IRではそれぞれ

    br label %while_cond

  while_cond:
    %5 = load i8*, i8** %%ptr
    %6 = load i8, i8* %5
    %7 = icmp ne i8 %6, 0
    br i1 %7, label %while_body, label %while_end

  while_body:

と

    br label %while_cond

  while_end:

に対応します。 Brainf**kのコードではループは何度も出てくるので、while_cond6 .. while_body6 .. while_end6のように数字をつけてラベルを区別する必要があります。 前回はこの番号をemit_while_startに渡してIRを直接出力していましたが、今回はジャンプする時にllvm::BasicBlock*を使う必要があるため、構造体を作って管理してみました。

struct WhileBlock {
  llvm::BasicBlock* cond_block;
  llvm::BasicBlock* body_block;
  llvm::BasicBlock* end_block;
};

void emit_while_start(llvm::Function* func, llvm::Value* ptr, WhileBlock* while_block, int while_index) {
  while_block->cond_block = llvm::BasicBlock::Create(
      TheContext, std::string("while_cond") + std::to_string(while_index), func);
  while_block->body_block = llvm::BasicBlock::Create(
      TheContext, std::string("while_body") + std::to_string(while_index), func);
  while_block->end_block = llvm::BasicBlock::Create(
      TheContext, std::string("while_end") + std::to_string(while_index), func);
  Builder.CreateBr(while_block->cond_block);
  Builder.SetInsertPoint(while_block->cond_block);
  Builder.CreateCondBr(
      Builder.CreateICmpNE(
        Builder.CreateLoad(Builder.CreateLoad(ptr)),
        Builder.getInt8(0)),
      while_block->body_block,
      while_block->end_block);
  Builder.SetInsertPoint(while_block->body_block);
}

void emit_while_end(WhileBlock* while_block) {
  Builder.CreateBr(while_block->cond_block);
  Builder.SetInsertPoint(while_block->end_block);
}

// ...
  int while_index = 0;
  WhileBlock while_blocks[1000];
  WhileBlock* while_block_ptr = while_blocks;

// ...
      case '[': emit_while_start(mainFunc, ptr, while_block_ptr++, while_index++); break;
      case ']': emit_while_end(--while_block_ptr); break;

llvm::BasicBlock::Createが関数の最後にブロックをつくるというのと、Builder.SetInsertPointでIRを吐くブロックを移動するということを理解しておけば、そんなに難しくないと思います。

 $ g++ `llvm-config --cxxflags --ldflags --libs --system-libs` bf2llvm.cpp -o bf2llvm
 $ echo "+++++++++[>++++++++>+++++++++++>+++++<<<-]>.>++.+++++++..+++.>-.------------.<++++++++.--------.+++.------.--------.>+." | ./bf2llvm 2>&1 | lli
Hello, world!
 $ cat prime.bf
++++++++++[->+++++>++++>+++<<<]>>++++>++>>+>+++<<<<<.>>>>>[<[-]++<[-]+>>>+[<[->>
+<<]<[->>>>+>+<<<<<]>>>>[-<<<<+>>>>]<[->+>-[>+>>]>[+[-<+>]>+>>]<<<<<<]>[-<<<+>>>
]>[-]>[-<<+>+>]<<[->>+<<]+>[<[-]>[-]]<[<<<<<[-]>>>>>[-]]>[-]>[-]>[-]<<<<<<-<[->>
>+>+<<<<]>>>>[-<<<<+>>>>]<<<[->>>>+>+<<<<<]>>>>>[-<<<<<+>>>>>]<<<+[->>[->+>+<<]>
>[-<<+>>]+<[>-<<->[-]]>[<<<+<[-]>>>>[-]]<[-]<<<]>>[-]<[<<->>[-]]<[-]<<+<[->>>+>+
<<<<]>>>>[-<<<<+>>>>]>+++++++++++++<<[->>[->+>+<<]>>[-<<+>>]+<[>-<<->[-]]>[<<<+<
[-]>>>>[-]]<[-]<<<]>>[-]<[<<[-[-]]>>[-]]<[-]<<<+>>]<<<[<.>>>>>++++++++++<<[->+>-
[>+>>]>[+[-<+>]>+>>]<<<<<<]>[-<+>]>[-]>>>++++++++++<[->-[>+>>]>[+[-<+>]>+>>]<<<<
<]>[-]>>[>++++++[-<++++++++>]<.<<+>+>[-]]<[<[->-<]++++++[->++++++++<]>.[-]]>[-]<
<<++++++[-<++++++++>]<.[-]<<<<<[-]]>>+]
 $ cat prime.bf | ./bf2llvm 2>&1 | /usr/local/opt/llvm/bin/lli
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251

大丈夫そうですね。

オブジェクトファイルを生成しよう

ここまでTheModule->dump()を使ってLLVM IRを出力してきました。 しかし、これでは実行するためにlliが必要となり、結局LLVMツールチェインの入ってない環境では動かすことができません。 KaleidoscopeのChapter 8を参考にしながら (まったく同じです。まだ理解が追いついてなくて…)、オブジェクトファイルを生成してみましょう。

TargetTripleとは、アーキテクチャ, ベンダー, プラットフォームのことです。 clang --version | grep Targetで確認することができます。 私の手元ではx86_64-apple-darwin15.6.0でした。

  std::string TargetTriple = llvm::sys::getDefaultTargetTriple();

このTargetTripleに対応するtargetを引きます。

  std::string err;
  const llvm::Target* Target = llvm::TargetRegistry::lookupTarget(TargetTriple, err);
  if (!Target) {
    std::cerr << "Failed to lookup target " + TargetTriple + ": " + err;
    return 1;
  }

CPUを指定します。 この指定によってメモリーalignmentやendiannessなどが変わるようです。

  llvm::TargetOptions opt;
  llvm::TargetMachine* TheTargetMachine = Target->createTargetMachine(
      TargetTriple, "generic", "", opt, llvm::Optional<llvm::Reloc::Model>());

ここで引いたtargetとtarget machineを、私たちのモジュールにセットします。

  TheModule->setTargetTriple(TargetTriple);
  TheModule->setDataLayout(TheTargetMachine->createDataLayout());

オブジェクトファイルを開いて

  std::string Filename = "output.o";
  std::error_code err_code;
  llvm::raw_fd_ostream dest(Filename, err_code, llvm::sys::fs::F_None);
  if (err_code) {
    std::cerr << "Could not open file: " << err_code.message();
    return 1;
  }

書き込んで終わりです。

  llvm::legacy::PassManager pass;
  if (TheTargetMachine->addPassesToEmitFile(pass, dest, llvm::TargetMachine::CGFT_ObjectFile)) {
    std::cerr << "TheTargetMachine can't emit a file of this type\n";
    return 1;
  }
  pass.run(*TheModule);
  dest.flush();

動かしてみましょう。

 $ g++ `llvm-config --cxxflags --ldflags --libs --system-libs` bf2llvm.cpp -o bf2llvm
 $ echo "+++++++++[>++++++++>+++++++++++>+++++<<<-]>.>++.+++++++..+++.>-.------------.<++++++++.--------.+++.------.--------.>+." | ./bf2llvm
Wrote output.o
 $ gcc output.o
 $ ./a.out
Hello, world!
 $ cat fibonacci.bf
>>+++++++++++[-<<++++>+++>>+<]>>+<++<<->>[>>>++++++++++<<[->+>-[>+>>]>[+[-<+>]>+
>>]<<<<<<]>>[-]>>>++++++++++<[->-[>+>>]>[+[-<+>]>+>>]<<<<<]>[-]>>[>++++++[-<++++
++++>]<.<<+>+>[-]]<[<[->-<]++++++[->++++++++<]>.[-]]<<++++++[-<++++++++>]<.[-]<<
[-<+>]<<[->>+>+<<<]>>>[-<<<+>>>]<-[<<<<<.>.>>>>[-]]<[->+>+<<]>>[-<<+>>]<<<<[->>+
<<]>>>[-<<<+>>>]<<-]
 $ cat fibonacci.bf | ./bf2llvm
Wrote output.o
 $ gcc output.o
 $ ./a.out
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233

きちんと動いてそうですね。

まとめ

Brainf**kのソースコードを受け取り、オブジェクトファイルを生成するコンパイラを作ることができました。 LLVM APIを使うことで、以下のような恩恵がありました。

• 一時変数のインデックスをいちいち管理しなくてよい
• オブジェクトファイルを生成することができる
• IRの命令が抽象化されており、おかしなIRを吐く確率が減る
• IRを直接書いていると、外部の関数のdeclareを書かなければいけなかったが、getOrInsertFunctionを使うと気にする必要がなくなる

APIを使ってコードを書くことは意外と骨が折れる事で、結局doxygenの生成ドキュメントを行ったり来たりしながら試行錯誤する必要がありました。 意外だったことは、IRのシンタックス的におかしなコードを吐くこともあるということです。 例えば

  llvm::Value* a = Builder.CreateAlloca(Builder.getInt32Ty(), nullptr, "a");
  Builder.CreateAdd(Builder.CreateLoad(a), Builder.getInt8(8));

このコードは次のようなコードを吐きます。

  %1 = load i32, i32* %a
  %2 = add i32 %1, i8 8

実行してみるとエラーになります。

lli: <stdin>:7:20: error: expected value token
  %2 = add i32 %1, i8 8
                   ^

型が違う、ではなくてシンタックスエラーになることもあるんですね。 将来挙動が変わるかもしれませんが。

前回の記事で、ある程度LLVM IRに慣れ親しんでいたために、IRBuilderもかなり楽に触ることができました。 逆に、IRの命令をなにも知らずにIRBuilderでコード生成するのはかなり難しいと思います。 対応するCのコードがあって、対応するLLVM IRコードがあって、それを出力するようなIRBuilderの関数を探します。 Brainf**kのコンパイラ作りを通じてかなりLLVMの世界の雰囲気がわかってきました。 そろそろKaleidoscopeを参考にしながら、実用的なシンタックスを持つ言語のコンパイラを作ってみようと思います。

ソースコード

github.com

bf2llvm.cpp

/*
 * Brainf**k compiler based on LLVM API
 *  $ g++ `llvm-config --cxxflags --ldflags --libs --system-libs` bf2llvm.cpp -o bf2llvm
 *  $ echo "+++++++++[>++++++++>+++++++++++>+++++<<<-]>.>++.+++++++..+++.\
            >-.------------.<++++++++.--------.+++.------.--------.>+." | \
            ./bf2llvm
 *  $ gcc output.o
 *  $ ./a.out
 */
#include <iostream>
#include <string>
#include "llvm/ADT/Optional.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/LegacyPassManager.h"
#include "llvm/IR/Module.h"
#include "llvm/Support/FileSystem.h"
#include "llvm/Support/TargetRegistry.h"
#include "llvm/Support/TargetSelect.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetOptions.h"

static llvm::LLVMContext TheContext;
static llvm::IRBuilder<> Builder(TheContext);
static std::unique_ptr<llvm::Module> TheModule;

void emit_move_ptr(llvm::Value* ptr, int diff) {
  Builder.CreateStore(
      Builder.CreateInBoundsGEP(
        Builder.getInt8Ty(),
        Builder.CreateLoad(ptr),
        Builder.getInt32(diff)),
      ptr);
}

void emit_add(llvm::Value* ptr, int diff) {
  llvm::Value* tmp = Builder.CreateLoad(ptr);
  Builder.CreateStore(
      Builder.CreateAdd(
        Builder.CreateLoad(tmp),
        Builder.getInt8(diff)),
      tmp);
}

void emit_put(llvm::Value* ptr) {
  llvm::Function* funcPutChar = llvm::cast<llvm::Function>(
      TheModule->getOrInsertFunction("putchar",
        Builder.getInt32Ty(),
        Builder.getInt32Ty(),
        nullptr));
  Builder.CreateCall(
      funcPutChar,
      Builder.CreateSExt(
        Builder.CreateLoad(Builder.CreateLoad(ptr)),
        Builder.getInt32Ty()));
}

void emit_get(llvm::Value* ptr) {
  llvm::Function* funcGetChar = llvm::cast<llvm::Function>(
      TheModule->getOrInsertFunction("getchar",
        Builder.getInt32Ty(),
        nullptr));
  Builder.CreateStore(
      Builder.CreateTrunc(
        Builder.CreateCall(funcGetChar),
        Builder.getInt8Ty()),
      Builder.CreateLoad(ptr));
}

struct WhileBlock {
  llvm::BasicBlock* cond_block;
  llvm::BasicBlock* body_block;
  llvm::BasicBlock* end_block;
};

void emit_while_start(llvm::Function* func, llvm::Value* ptr, WhileBlock* while_block, int while_index) {
  while_block->cond_block = llvm::BasicBlock::Create(
      TheContext, std::string("while_cond") + std::to_string(while_index), func);
  while_block->body_block = llvm::BasicBlock::Create(
      TheContext, std::string("while_body") + std::to_string(while_index), func);
  while_block->end_block = llvm::BasicBlock::Create(
      TheContext, std::string("while_end") + std::to_string(while_index), func);
  Builder.CreateBr(while_block->cond_block);
  Builder.SetInsertPoint(while_block->cond_block);
  Builder.CreateCondBr(
      Builder.CreateICmpNE(
        Builder.CreateLoad(Builder.CreateLoad(ptr)),
        Builder.getInt8(0)),
      while_block->body_block,
      while_block->end_block);
  Builder.SetInsertPoint(while_block->body_block);
}

void emit_while_end(WhileBlock* while_block) {
  Builder.CreateBr(while_block->cond_block);
  Builder.SetInsertPoint(while_block->end_block);
}

int main() {
  TheModule = llvm::make_unique<llvm::Module>("top", TheContext);
  llvm::Function* mainFunc = llvm::Function::Create(
      llvm::FunctionType::get(llvm::Type::getInt32Ty(TheContext), false),
      llvm::Function::ExternalLinkage, "main", TheModule.get());
  Builder.SetInsertPoint(llvm::BasicBlock::Create(TheContext, "", mainFunc));

  llvm::Value* data = Builder.CreateAlloca(Builder.getInt8PtrTy(), nullptr, "data");
  llvm::Value* ptr = Builder.CreateAlloca(Builder.getInt8PtrTy(), nullptr, "ptr");
  llvm::Function* funcCalloc = llvm::cast<llvm::Function>(
      TheModule->getOrInsertFunction("calloc",
        Builder.getInt8PtrTy(),
        Builder.getInt64Ty(), Builder.getInt64Ty(),
        nullptr));
  llvm::Value* data_ptr = Builder.CreateCall(funcCalloc, {Builder.getInt64(30000), Builder.getInt64(1)});
  Builder.CreateStore(data_ptr, data);
  Builder.CreateStore(data_ptr, ptr);

  int while_index = 0;
  WhileBlock while_blocks[1000];
  WhileBlock* while_block_ptr = while_blocks;
  char c;
  while (std::cin.get(c)) {
    switch (c) {
      case '>': emit_move_ptr(ptr, 1); break;
      case '<': emit_move_ptr(ptr, -1); break;
      case '+': emit_add(ptr, 1); break;
      case '-': emit_add(ptr, -1); break;
      case '[': emit_while_start(mainFunc, ptr, while_block_ptr++, while_index++); break;
      case ']': if (--while_block_ptr < while_blocks) {
                  std::cerr << "unmatching ]\n";
                  return 1;
                }
                emit_while_end(while_block_ptr); break;
      case '.': emit_put(ptr); break;
      case ',': emit_get(ptr); break;
    }
  }

  llvm::Function* funcFree = llvm::cast<llvm::Function>(
      TheModule->getOrInsertFunction("free",
        Builder.getVoidTy(),
        Builder.getInt8PtrTy(),
        nullptr));
  Builder.CreateCall(funcFree, {Builder.CreateLoad(data)});

  Builder.CreateRet(Builder.getInt32(0));

  llvm::InitializeAllTargetInfos();
  llvm::InitializeAllTargets();
  llvm::InitializeAllTargetMCs();
  llvm::InitializeAllAsmParsers();
  llvm::InitializeAllAsmPrinters();

  std::string TargetTriple = llvm::sys::getDefaultTargetTriple();

  std::string err;
  const llvm::Target* Target = llvm::TargetRegistry::lookupTarget(TargetTriple, err);
  if (!Target) {
    std::cerr << "Failed to lookup target " + TargetTriple + ": " + err;
    return 1;
  }

  llvm::TargetOptions opt;
  llvm::TargetMachine* TheTargetMachine = Target->createTargetMachine(
      TargetTriple, "generic", "", opt, llvm::Optional<llvm::Reloc::Model>());

  TheModule->setTargetTriple(TargetTriple);
  TheModule->setDataLayout(TheTargetMachine->createDataLayout());

  std::string Filename = "output.o";
  std::error_code err_code;
  llvm::raw_fd_ostream dest(Filename, err_code, llvm::sys::fs::F_None);
  if (err_code) {
    std::cerr << "Could not open file: " << err_code.message();
    return 1;
  }

  llvm::legacy::PassManager pass;
  if (TheTargetMachine->addPassesToEmitFile(pass, dest, llvm::TargetMachine::CGFT_ObjectFile)) {
    std::cerr << "TheTargetMachine can't emit a file of this type\n";
    return 1;
  }
  pass.run(*TheModule);
  dest.flush();
  std::cout << "Wrote " << Filename << "\n";

  return 0;
}