LLVMを始めよう！ 〜 LLVM IRの基礎はclangが教えてくれた・Brainf**kコンパイラを作ってみよう 〜

コンパイラを作ってみたいと思っていても、アセンブリ言語はよくわからない。 パーサーみたいなコードは書いたことがあるけれど、コード生成の処理はさっぱりだ。 実行ファイルをバイナリエディターで見るとかなにそれ怖い。

そんな私なのですが、LLVMに興味を持ち始めています。 SwiftやRust、あるいはEmscriptenなど、近年注目されている言語やコンパイラ技術の中枢にはLLVMがあります。 アセンブリはよく分からなくてもLLVMを使いこなせるようになれば、マルチプラットフォームで実行ファイルを生成できる言語処理系を作るのではないか。 コンパイラ作ってみたいな、LLVMを使ってみようかなと思っている今日このごろです。

ところが、いざLLVMを勉強しようと思ってもどこから始めればいいかよく分かりませんでした。 マニュアルは巨大で読む気が起きないし、リファレンスを見てもさっぱりです。 雰囲気はわかるんです、インストラクションっていうのはプリミティブな命令のことでしょう、そのリファレンスは便利なんでしょう。 でも素人にはどこから手を付けてよいのかわからない。 LLVMを用いた処理系の入門として名高いKaleidoscopeをやってみようかなと思って始めても、Lexerを作ってParserを作って、「ああ、C++なんて久々に書いたなぁ」なんて言っているうちにLLVM IRにたどり着かずに飽きてしまう。 C++が肌に合わないんだと思ってGo言語のLLVM bindingを使ってコードを書こうとしても、Go bindingのソースコードとLLVM本体のコードをあっちこっち飛んで回って疲弊してしまう。 他の人が作った処理系のコードを読んでみようと思ってcloneしてみても、いつの間にか読む暇もなく忘れてしまう。

こんなダメダメな私はいったいどうすればいいのかと思って調べていたのですが、ある日次のようなブログ記事を見つけました。 そうだ、こんな簡単なことを忘れていた。 LLVMを使っているとても身近なコンパイラがあるじゃないか！ 私は慌ててこのブログの人と同じことをしてみました (本記事はLLVMがインストールされており、LLVMツールのパスが通っていることを前提とします。私の手元では/usr/local/opt/llvm/bin/でした)。

 $ cat > test.c <<EOF
int main() {
  return 42;
}
EOF
 $ clang -S -emit-llvm -O2 test.c
 $ lli test.ll
 $ echo $?
42

これなら私にもできる！ 高ぶる気持ちを抑えて実行ファイル生成まで試してみます。

 $ llc test.ll
 $ gcc test.s -o test
 $ ./test
 $ echo $?
42

実行ファイルを生成し、実行することができました。

clang -S -emit-llvmが生成したファイル、test.llをおそるおそる覗いてみます。

test.ll

; ModuleID = 'test.c'
source_filename = "test.c"
target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-apple-macosx10.12.0"

; Function Attrs: norecurse nounwind readnone ssp uwtable
define i32 @main() #0 {
  ret i32 42
}

attributes #0 = { norecurse nounwind readnone ssp uwtable "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="penryn" "target-features"="+cx16,+fxsr,+mmx,+sse,+sse2,+sse3,+sse4.1,+ssse3" "unsafe-fp-math"="false" "use-soft-float"="false" }

!llvm.module.flags = !{!0}
!llvm.ident = !{!1}

!0 = !{i32 1, !"PIC Level", i32 2}
!1 = !{!"Apple LLVM version 8.0.0 (clang-800.0.42.1)"}

うーん、これはさっぱりです。 とりあえずコメントなどいらなさそうな物を削ってみて、どれだけ消しても動くか試してみます。

test.ll

source_filename = "test.c"

define i32 @main() #0 {
  ret i32 42
}

attributes #0 = { norecurse nounwind readnone ssp uwtable "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="penryn" "target-features"="+cx16,+fxsr,+mmx,+sse,+sse2,+sse3,+sse4.1,+ssse3" "unsafe-fp-math"="false" "use-soft-float"="false" }

 $ lli test.ll; echo $?
42

動きます。 #0と書いてあるのがよく分からないですが消してみます。

test.ll

define i32 @main() {
  ret i32 42
}

 $ lli test.ll; echo $?
42

動きました。なんだ、source_filenameもなくても動くんですね…

改めて最も小さくなったLLVM IR (Intermediate representation, 中間表現) のコードを眺めてみます。

test.ll

define i32 @main() {
  ret i32 42
}

defineで関数を定義しているのかな、retはreturnだろうな、i32は32bit intなんだろなと、容易に想像が付きます。 こんな小さいコードなら、手で書くこともできそうです。 そうです、すでにdefine, ret, i32といったキーワードを理解し始めているのです。

ここまでやったことはとても簡単で、しかもすぐに試せることです。 とても小さなCのコードを書き、clang -S -emit-llvmでLLVM IRファイルを生成し、lliã‚„llcといったコマンドで実行できることを確かめながら、ファイルを削って本当に必要な部分を探しただけです。 LLVMのリファレンスは全く見なくても、Cのどういうコードがどういう命令列になるかはclangが教えてくれるのです。

この方法なら、長いリファレンスや入門チュートリアルを読まなくても、一歩ずつ着実にLLVM IRを学んでいけるのです。

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

基本的な命令を学ぼう

int main()と書くとdefine i32 @main()となることや、return 42がret i32 42となることはわかりました。 しかしこれだけでは何もできないので、いくつか基本的な文を変換してみてLLVM IRがどうなるかを調べてみましょう。

まず、変数の宣言を調べてみます。 次のようなコードを書いてみます。

test.c

int main() {
  char c;
  int i;
  long l;
}

これのLLVM IRを見てみます。-O0で最適化されないように気をつけます。

 $ clang -S -emit-llvm -O0 test.c
 $ cat test.ll

コメントやattributesなどを削除したら次のようになります。

test.ll

define i32 @main() {
  %1 = alloca i8, align 1
  %2 = alloca i32, align 4
  %3 = alloca i64, align 8
  ret i32 0
}

実際このファイルは実行できます。

 $ lli test.ll

一行ずつ見比べると、charがi8, intがi32, longがi64に対応していることがわかります。 alignはアドレスのアラインメントを表しており、変数のアドレスがこの数字の倍数であることが保証されます。

次に代入を調べます。 先程のコードに代入を追加して調べてみます。

test.c

int main() {
  char c;
  int i;
  long l;
  c = 'a';
  i = 72;
  l = 123456789012345;
}

このコードのLLVM IRは次のようになります。

test.ll

define i32 @main() {
  %1 = alloca i8, align 1
  %2 = alloca i32, align 4
  %3 = alloca i64, align 8
  store i8 97, i8* %1, align 1
  store i32 72, i32* %2, align 4
  store i64 123456789012345, i64* %3, align 8
  ret i32 0
}

store命令となりました。 第一引数が代入したい値で、第二引数が代入先のアドレスとなるようです。

少しコードを変えてみます。

test.c

int main() {
  char a, b;
  a = 32;
  b = a;
}

このコードのLLVM IRは次のようになります。

test.ll

define i32 @main() {
  %1 = alloca i8, align 1
  %2 = alloca i8, align 1
  store i8 32, i8* %1, align 1
  %3 = load i8, i8* %1, align 1
  store i8 %3, i8* %2, align 1
  ret i32 0
}

%1に32を保存し、%1の値をload命令で取り出して%3とし、それを%2にstoreしています。

足し算や引き算するとどうなるでしょうか。int同士の足し引きを見てみます。

test.c

int main() {
  int a, b, c;
  a = 32;
  b = a + 24;
  c = b - a;
}

test.ll

define i32 @main() {
  ; int a, b, c
  %1 = alloca i32, align 4
  %2 = alloca i32, align 4
  %3 = alloca i32, align 4

  ; a = 32
  store i32 32, i32* %1, align 4

  ; b = a + 24
  %4 = load i32, i32* %1, align 4
  %5 = add nsw i32 %4, 24
  store i32 %5, i32* %2, align 4

  ; c = b - a
  %6 = load i32, i32* %2, align 4
  %7 = load i32, i32* %1, align 4
  %8 = sub nsw i32 %6, %7
  store i32 %8, i32* %3, align 4

  ret i32 0
}

やはり足し算はadd命令, 引き算はsub命令となりました。 nswは理解を後回しして良いでしょう。

後は標準出力が気になります。Hello worldのLLVM IRを見てみます。

test.c

#include <stdio.h>
int main() {
  printf("Hello, world!\n");
}

test.ll

@.str = private unnamed_addr constant [15 x i8] c"Hello, world!\0A\00", align 1

define i32 @main() {
  %1 = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([15 x i8], [15 x i8]* @.str, i32 0, i32 0))
  ret i32 0
}

declare i32 @printf(i8*, ...)

declare命令でprintfを使うことを宣言し、call命令で呼び出しを行っています。 printfではなくてputcharを使ってみます。

test.c

#include <stdio.h>
int main() {
  char c;
  c = 'a';
  putchar(c);
}

test.ll

define i32 @main() {
  %1 = alloca i8, align 1
  store i8 97, i8* %1, align 1
  %2 = load i8, i8* %1, align 1
  %3 = sext i8 %2 to i32
  %4 = call i32 @putchar(i32 %3)
  ret i32 0
}

declare i32 @putchar(i32)

よく見ると、loadしてputcharするだけではなくて、sext命令が入っています。 そういえばputcharの引数はcharではなくてintでしたね。 sextはsigned extendの略で、型の変換を行う命令です。

Brainf**kのコンパイラを作ってみよう

宣言・代入・演算そして関数と、とても基本的なコードがLLVM IRでどのようになるかを観察してきました。 これだけでは実用的なプログラミング言語のコンパイラを作るには知識が足りないのですが、プリミティブな言語の処理系なら作れる気がしてきました。

プリミティブな言語…といえばBrainf**kですよね。 私はこの言語が大好きです。 言語処理系のHello worldと言ってもいいのではないでしょうか。 先ほど紹介した記事でも、Brainf**kのコンパイラを書いています。 目的が同じですが、そっくり真似にならないようにちら見程度にして、自分の手で書いてみようと思います。

まずはBrainf**kのデータ領域の用意をします。

test.c

#include <stdlib.h>

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

このLLVM IRを見てみましょう。

test.ll

define i32 @main() {
  %1 = alloca i8*, align 8
  %2 = alloca i8*, align 8

  %3 = call i8* @calloc(i64 30000, i64 1)
  store i8* %3, i8** %1, align 8

  %4 = load i8*, i8** %1, align 8
  store i8* %4, i8** %2, align 8

  %5 = load i8*, i8** %1, align 8
  call void @free(i8* %5)
  ret i32 0
}

declare i8* @calloc(i64, i64)

declare void @free(i8*)

i8*型の変数dataとptrを作り、callocの結果を代入しています。

次に、ポインターの移動>とインクリメント+に対応するCのコードを、LLVM IRで見てみます。

test.ll

  ; >   ++ptr
  %5 = load i8*, i8** %2, align 8
  %6 = getelementptr inbounds i8, i8* %5, i32 1
  store i8* %6, i8** %2, align 8

  ; +   ++*ptr
  %7 = load i8*, i8** %2, align 8
  %8 = load i8, i8* %7, align 1
  %9 = add i8 %8, 1
  store i8 %9, i8* %7, align 1

getelementptrという新しい命令が出てきましたね。 意味は後で調べるとして、今はこういうものだと思っておきましょう。 ++*ptrは、ptrの値を%7に入れて、pointer dereferenceして%8に入れて、1足して%9に入れて、それを%7に代入する、と一行ずつ意味を読み取りやすいですね。

あとBrainf**kの.命令に対応するputchar(*ptr);のコードを見ておきます。

test.ll

  ; .  putchar(*ptr)
  %5 = load i8*, i8** %2, align 8
  %6 = load i8, i8* %5, align 1
  %7 = sext i8 %6 to i32
  %8 = call i32 @putchar(i32 %7)

そうでした、sext (signed extend) 命令でi32に変換する必要がありましたね。

Brainf**kの>, +, .に対応するLLVM IRコードが分かりました。<, -のコードも容易に想像がつきます。 ようやく道具が揃ったので、Brainf**kのLLVM IRコンパイラを書いてみます。

bf2llvm.c

#include <stdio.h>
#include <stdlib.h>

void emit_header() {
  printf("define i32 @main() {\n");
  printf("  %%data = alloca i8*, align 8\n");
  printf("  %%ptr = alloca i8*, align 8\n");
  printf("  %%data_ptr = call i8* @calloc(i64 30000, i64 1)\n");
  printf("  store i8* %%data_ptr, i8** %%data, align 8\n");
  printf("  store i8* %%data_ptr, i8** %%ptr, align 8\n");
}

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_add(int diff) {
  printf("  %%%d = load i8*, i8** %%ptr, align 8\n", idx);
  printf("  %%%d = load i8, i8* %%%d, align 1\n", idx + 1, idx);
  printf("  %%%d = add i8 %%%d, %d\n", idx + 2, idx + 1, diff);
  printf("  store i8 %%%d, i8* %%%d, align 1\n", idx + 2, idx);
  idx += 3;
}

void emit_put() {
  printf("  %%%d = load i8*, i8** %%ptr, align 8\n", idx);
  printf("  %%%d = load i8, i8* %%%d, align 1\n", idx + 1, idx);
  printf("  %%%d = sext i8 %%%d to i32\n", idx + 2, idx + 1);
  printf("  %%%d = call i32 @putchar(i32 %%%d)\n", idx + 3, idx + 2);
  idx += 4;
}

void emit_footer() {
  printf("  %%%d = load i8*, i8** %%data, align 8\n", idx);
  printf("  call void @free(i8* %%%d)\n", idx);
  printf("  ret i32 0\n");
  printf("}\n\n");
  printf("declare i8* @calloc(i64, i64)\n\n");
  printf("declare void @free(i8*)\n\n");
  printf("declare i32 @putchar(i32)\n");
}

int main() {
  char c;
  emit_header();
  while ((c = getchar()) != EOF) {
    switch (c) {
      case '>': emit_move_ptr(1); break;
      case '<': emit_move_ptr(-1); break;
      case '+': emit_add(1); break;
      case '-': emit_add(-1); break;
      case '.': emit_put(); break;
    }
  }
  emit_footer();
  return 0;
}

動かしてみます。

 $ gcc bf2llvm.c -o bf2llvm
 $ echo "+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++." | ./bf2llvm
define i32 @main() {
  %data = alloca i8*, align 8
  %ptr = alloca i8*, align 8
  %data_ptr = call i8* @calloc(i64 30000, i64 1)
  store i8* %data_ptr, i8** %data, align 8
  store i8* %data_ptr, i8** %ptr, align 8
  %1 = load i8*, i8** %ptr, align 8
  %2 = load i8, i8* %1, align 1
  %3 = add i8 %2, 1
  store i8 %3, i8* %1, align 1
  ; ç•¥
  store i8 %195, i8* %193, align 1
  %196 = load i8*, i8** %ptr, align 8
  %197 = load i8, i8* %196, align 1
  %198 = sext i8 %197 to i32
  %199 = call i32 @putchar(i32 %198)
  %200 = load i8*, i8** %data, align 8
  call void @free(i8* %200)
  ret i32 0
}

declare i8* @calloc(i64, i64)

declare void @free(i8*)

declare i32 @putchar(i32)
 $ echo "+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++." | ./bf2llvm | lli
A

やった！ これでは+と.しか試してないので他の命令も使ってみます。

 $ echo "++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.+++++++++++++++++++++++++++++.+++++++..+++.>++++++++++++++++++++++++++++++++.<++++++++.--------.+++.------.--------.>+." | ./bf2llvm | lli
Hello world!

動いてそうですね！ 最初の峠は超えたようです！

ループに対応しよう

Brainf**kの[, ]に対応しましょう。 まずはCで書いてclangでLLVM IRを調べてみます。 [はwhile (*ptr) {に、]は}に対応します。 以下のプログラムは、Brainf**kの++[>++<-]>.に対応するコードで、実行したら"\x04"を出力します。

test.c

#include <stdio.h>
#include <stdlib.h>

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

LLVM IRは次のようになりました。

test.ll

define i32 @main() {
  %1 = alloca i32, align 4
  %2 = alloca i8*, align 8
  %3 = alloca i8*, align 8
  store i32 0, i32* %1, align 4
  %4 = call i8* @calloc(i64 30000, i64 1)
  ; ç•¥
  store i8 %11, i8* %9, align 1
  br label %12

; <label>:12                                      ; preds = %16, %0
  %13 = load i8*, i8** %3, align 8
  %14 = load i8, i8* %13, align 1
  %15 = icmp ne i8 %14, 0
  br i1 %15, label %16, label %30

; <label>:16                                      ; preds = %12
  %17 = load i8*, i8** %3, align 8
  %18 = getelementptr inbounds i8, i8* %17, i32 1
  store i8* %18, i8** %3, align 8
  ; ç•¥
  store i8 %29, i8* %27, align 1
  br label %12

; <label>:30                                      ; preds = %12
  %31 = load i8*, i8** %3, align 8
  ; ç•¥
  ret i32 %38
}

declare i8* @calloc(i64, i64)

declare i32 @putchar(i32)

declare void @free(i8*)

while文のジャンプにbr (branch) 命令が、条件文に対応する場所はicmp (integer compare) が使われていることがわかります。 ; <label>:12は、見ての通りラベルで、br label %12でそこにジャンプしているのだと想像がつきます。 次のようにラベルを読みやすく書くこともできます。

  br label %while_cond0

while_cond0:
  ; ç•¥
  br i1 %14, label %while_body0, label %while_end0

while_body0:
  ; ç•¥
  br label %while_cond0

while_end0:

while文の出力の仕方が分かったので、コンパイラの続きを書いてみます。

bf2llvm.c

void emit_while_start(int while_index) {
  printf("  br label %%while_cond%d\n", while_index);
  printf("while_cond%d:\n", while_index);
  printf("  %%%d = load i8*, i8** %%ptr, align 8\n", idx);
  printf("  %%%d = load i8, i8* %%%d, align 1\n", idx + 1, idx);
  printf("  %%%d = icmp ne i8 %%%d, 0\n", idx + 2, idx + 1);
  printf("  br i1 %%%d, label %%while_body%d, label %%while_end%d\n", idx + 2, while_index, while_index);
  printf("while_body%d:\n", while_index);
  idx += 3;
}

void emit_while_end(int while_index) {
  printf("  br label %%while_cond%d\n", while_index);
  printf("while_end%d:\n", while_index);
}

/* ç•¥ */
int main() {
  char c;
  int while_index = 0;
  int while_indices[1000];
  int* while_index_ptr = while_indices;
  emit_header();
  while ((c = getchar()) != EOF) {
    switch (c) {
      /* ç•¥ */
      case '[': emit_while_start(*while_index_ptr++ = while_index++); break;
      case ']': emit_while_end(*--while_index_ptr); break;
    }
  }
  emit_footer();
  return 0;
}

試してみましょう。

 $ gcc bf2llvm.c -o bf2llvm
 $ echo "+++++++++[>++++++++>+++++++++++>+++++<<<-]>.>++.+++++++..+++.>-.------------.<++++++++.--------.+++.------.--------.>+." | ./bf2llvm | lli
Hello, world!

動いてそうですね！ もう少しややこしいコードを動かしてみます。

 $ cat fibonacci.bf
>>+++++++++++[-<<++++>+++>>+<]>>+<++<<->>[>>>++++++++++<<[->+>-[>+>>]>[+[-<+>]>+
>>]<<<<<<]>>[-]>>>++++++++++<[->-[>+>>]>[+[-<+>]>+>>]<<<<<]>[-]>>[>++++++[-<++++
++++>]<.<<+>+>[-]]<[<[->-<]++++++[->++++++++<]>.[-]]<<++++++[-<++++++++>]<.[-]<<
[-<+>]<<[->>+>+<<<]>>>[-<<<+>>>]<-[<<<<<.>.>>>>[-]]<[->+>+<<]>>[-<<+>>]<<<<[->>+
<<]>>>[-<<<+>>>]<<-]
 $ cat fibonacci.bf | ./bf2llvm | lli
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233
 $ cat prime.bf
++++++++++[->+++++>++++>+++<<<]>>++++>++>>+>+++<<<<<.>>>>>[<[-]++<[-]+>>>+[<[->>
+<<]<[->>>>+>+<<<<<]>>>>[-<<<<+>>>>]<[->+>-[>+>>]>[+[-<+>]>+>>]<<<<<<]>[-<<<+>>>
]>[-]>[-<<+>+>]<<[->>+<<]+>[<[-]>[-]]<[<<<<<[-]>>>>>[-]]>[-]>[-]>[-]<<<<<<-<[->>
>+>+<<<<]>>>>[-<<<<+>>>>]<<<[->>>>+>+<<<<<]>>>>>[-<<<<<+>>>>>]<<<+[->>[->+>+<<]>
>[-<<+>>]+<[>-<<->[-]]>[<<<+<[-]>>>>[-]]<[-]<<<]>>[-]<[<<->>[-]]<[-]<<+<[->>>+>+
<<<<]>>>>[-<<<<+>>>>]>+++++++++++++<<[->>[->+>+<<]>>[-<<+>>]+<[>-<<->[-]]>[<<<+<
[-]>>>>[-]]<[-]<<<]>>[-]<[<<[-[-]]>>[-]]<[-]<<<+>>]<<<[<.>>>>>++++++++++<<[->+>-
[>+>>]>[+[-<+>]>+>>]<<<<<<]>[-<+>]>[-]>>>++++++++++<[->-[>+>>]>[+[-<+>]>+>>]<<<<
<]>[-]>>[>++++++[-<++++++++>]<.<<+>+>[-]]<[<[->-<]++++++[->++++++++<]>.[-]]>[-]<
<<++++++[-<++++++++>]<.[-]<<<<<[-]]>>+]
 $ cat prime.bf | ./bf2llvm | 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

Erik Bosmanさんという方が書いた、マンデルブロ集合のプログラムも動かすことができます。 出力は読者が確認してください。

基本構文に対応できてそれらを使った小さなコードが動いてしまえば、あらゆるプログラムが動く (とは言えメモリーの限界はありますが) というのはコンパイラの分野でコード書いていて楽しい所です。

最適化

LLVMにはLLVM IRレベルの命令列を最適化する機能があります。 LLVMをバックエンドに持つコンパイル言語は、LLVMの最適化の恩恵を受けられます。

LLVM IR命令列がどのように最適化されるかを調べるには、optコマンドを使うとよいでしょう。

 $ cat hello.bf 
+++++++++[>++++++++>+++++++++++>+++++<<<-]>.>++.+++++++..+++.>-.------------.<++++++++.--------.+++.------.--------.>+.
 $ cat hello.bf | ./bf2llvm | opt -S -O3
; ModuleID = '<stdin>'
source_filename = "<stdin>"

; Function Attrs: nounwind
define i32 @main() local_unnamed_addr #0 {
while_end0:
  %0 = tail call i32 @putchar(i32 72)
  %1 = tail call i32 @putchar(i32 101)
  %2 = tail call i32 @putchar(i32 108)
  %3 = tail call i32 @putchar(i32 108)
  %4 = tail call i32 @putchar(i32 111)
  %5 = tail call i32 @putchar(i32 44)
  %6 = tail call i32 @putchar(i32 32)
  %7 = tail call i32 @putchar(i32 119)
  %8 = tail call i32 @putchar(i32 111)
  %9 = tail call i32 @putchar(i32 114)
  %10 = tail call i32 @putchar(i32 108)
  %11 = tail call i32 @putchar(i32 100)
  %12 = tail call i32 @putchar(i32 33)
  ret i32 0
}

; Function Attrs: nounwind
declare i32 @putchar(i32) local_unnamed_addr #0

attributes #0 = { nounwind }

なんと、IO以外は全て計算されてしまいました！ もともと配列を確保してその上で計算していたはずが、最適化によってそれも消えてしまいました。

もう少し複雑な、マンデルブロ集合のスクリプトで実行時間を比較してみましょう。

 $ time sh -c 'cat mandelbrot.b | ./bf2llvm | lli > /dev/null'
        6.34 real         6.27 user         0.04 sys
 $ time sh -c 'cat mandelbrot.b | ./bf2llvm | opt -S -O3 | lli > /dev/null'
        3.55 real         3.50 user         0.05 sys

LLVMの最適化によって約40%も高速化しました (Hello worldほど単純ではないので、配列ごと消えるということはありません)。 コンパイルして実行ファイルを作ってみます。

 $ cat mandelbrot.b | ./bf2llvm | opt -S -O3 > mandelbrot.ll
 $ llc mandelbrot.ll
 $ gcc mandelbrot.s -o mandelbrot
 $ time ./mandelbrot > /dev/null
        0.98 real         0.97 user         0.00 sys

はい。すごく速いですね。 手でBrainf**kのインタープリタを書いて最適化しようとしても、小手先の改善の組み合わせでLLVMレベルの最適化するのは難しいでしょう。 まずは素朴に命令列を吐いて、最適化をおまかせしてしまえば速度が出るとてもうれしいですね。 私のようにアセンブリの分からない人でも、LLVM IRを正しく吐くことさえできれば実行ファイル生成まで面倒見てくれるのはLLVMの素晴らしいところですね。

まとめ

LLVMの最初の一歩はLLVM IRの命令と親しむところにあります。 しかし多くのチュートリアルでは、難しい言語をC++でパースして構文木を作ってIRを吐いてという説明から始まります。 できる人にはできるのでしょうが、私には理解が追いつきませんでした。 LLVM IRを初めて触った人が、いきなりIRBuilderからコード生成できるのでしょうか。 LLVM素人がいきなりIRBuilderのメソッド一覧を眺めて、これを使えばいいなみたいにすぐに分かるものなのでしょうか。

そんな人にとって、clangは良い先生だと思います。 CのコードがどのようなLLVM IRの命令列になるか教えてくれます。 CとLLVM IRを見比べながら、自分でも命令列を吐くコードを書いてみて、徐々に分かっていくものだと思います。 それはIRBuilderを使ったコードに比べたら泥臭いコードかもしれませんが、入門の壁を超える大事な一歩だと思います。

この記事は、実際に私自身が一歩ずつ理解を深めながら、同時並行して書き進めてきました。 私はLLVMについてはド素人で、Kaleidoscopeレベルにすら到達していません。

そんな私だからこそ、この記事を書こうと思った時には今の私に書ける「Kaleidoscopeの手前のLLVM入門記事にしよう」という思いがありました。 LLVMを触ってみたいけど、最初の壁が超えられない、そういった人に届けばいいなと思います。

いくつかの命令についてあまり説明せずに通り過ぎたところがありました。 命令の正確な意味や引数などの理解を深めるためには、言語マニュアルを参照してください。 なお、用語や記述には気をつけて書いていますが、誤りがあればご指摘ください。

LLVMのページを開いた時、命令の説明書をぼーっと眺めている時、このツールは私に使えるものなのだろうかという不安がありました。 今の気持ちは全く違います。 実際に触って試行錯誤したら、コツが分かってきました。 ようやくLLVMの世界の入り口に立った気持ちです。 IRの命令の雰囲気が掴めてきたので、次はIRBuilderを使ったコード生成や、実用的な言語のコンパイラ作成に挑戦してみようと思います。 今後も理解を深め、コンパイラ技術の勉強を続けていこうと思います。

続きです。 itchyny.hatenablog.com

ソースコード

bf2llvm.c

/*
 * Brainf**k -> LLVM IR Compiler
 *  $ gcc bf2llvm.c -o bf2llvm
 *  $ echo "+++++++++[>++++++++>+++++++++++>+++++<<<-]>.>++.+++++++..+++.\
            >-.------------.<++++++++.--------.+++.------.--------.>+." | \
            ./bf2llvm | opt -S -O3 | lli
 */
#include <stdio.h>
#include <stdlib.h>

void emit_header() {
  printf("define i32 @main() {\n");
  printf("  %%data = alloca i8*, align 8\n");
  printf("  %%ptr = alloca i8*, align 8\n");
  printf("  %%data_ptr = call i8* @calloc(i64 30000, i64 1)\n");
  printf("  store i8* %%data_ptr, i8** %%data, align 8\n");
  printf("  store i8* %%data_ptr, i8** %%ptr, align 8\n");
}

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_add(int diff) {
  printf("  %%%d = load i8*, i8** %%ptr, align 8\n", idx);
  printf("  %%%d = load i8, i8* %%%d, align 1\n", idx + 1, idx);
  printf("  %%%d = add i8 %%%d, %d\n", idx + 2, idx + 1, diff);
  printf("  store i8 %%%d, i8* %%%d, align 1\n", idx + 2, idx);
  idx += 3;
}

void emit_put() {
  printf("  %%%d = load i8*, i8** %%ptr, align 8\n", idx);
  printf("  %%%d = load i8, i8* %%%d, align 1\n", idx + 1, idx);
  printf("  %%%d = sext i8 %%%d to i32\n", idx + 2, idx + 1);
  printf("  %%%d = call i32 @putchar(i32 %%%d)\n", idx + 3, idx + 2);
  idx += 4;
}

void emit_get() {
  printf("  %%%d = call i32 @getchar()\n", idx);
  printf("  %%%d = trunc i32 %%%d to i8\n", idx + 1, idx);
  printf("  %%%d = load i8*, i8** %%ptr, align 8\n", idx + 2);
  printf("  store i8 %%%d, i8* %%%d, align 1\n", idx + 1, idx + 2);
  idx += 3;
}

void emit_while_start(int while_index) {
  printf("  br label %%while_cond%d\n", while_index);
  printf("while_cond%d:\n", while_index);
  printf("  %%%d = load i8*, i8** %%ptr, align 8\n", idx);
  printf("  %%%d = load i8, i8* %%%d, align 1\n", idx + 1, idx);
  printf("  %%%d = icmp ne i8 %%%d, 0\n", idx + 2, idx + 1);
  printf("  br i1 %%%d, label %%while_body%d, label %%while_end%d\n", idx + 2, while_index, while_index);
  printf("while_body%d:\n", while_index);
  idx += 3;
}

void emit_while_end(int while_index) {
  printf("  br label %%while_cond%d\n", while_index);
  printf("while_end%d:\n", while_index);
}

void emit_footer() {
  printf("  %%%d = load i8*, i8** %%data, align 8\n", idx);
  printf("  call void @free(i8* %%%d)\n", idx);
  printf("  ret i32 0\n");
  printf("}\n\n");
  printf("declare i8* @calloc(i64, i64)\n\n");
  printf("declare void @free(i8*)\n\n");
  printf("declare i32 @putchar(i32)\n\n");
  printf("declare i32 @getchar()\n");
}

int main() {
  char c;
  int while_index = 0;
  int while_indices[1000];
  int* while_index_ptr = while_indices;
  emit_header();
  while ((c = getchar()) != EOF) {
    switch (c) {
      case '>': emit_move_ptr(1); break;
      case '<': emit_move_ptr(-1); break;
      case '+': emit_add(1); break;
      case '-': emit_add(-1); break;
      case '[': emit_while_start(*while_index_ptr++ = while_index++); break;
      case ']': emit_while_end(*--while_index_ptr); break;
      case '.': emit_put(); break;
      case ',': emit_get(); break;
    }
  }
  emit_footer();
  return 0;
}