C++でBrainFuck->LLVM IRコンパイラを作ってみた
なんとなく自作プログラミング言語について勉強してみたいなーと思っていたところ、LLVM Tutorialを見つけたのでやってみることにしました。 ただ、私には圧倒的知識不足（言語処理系の知識、LLVMの知識、C言語・C++の知識がほぼない）という問題があり、始める前から苦戦する予感がビンビンでした。
とりあえず、C言語の入門サイト、C++の入門サイトでC言語・C++の基礎を学習し、その後、LLVM Tutorialに手をつけてみました。 ところが、LLVM TutorialのChapter4に入りC++のLLVM APIが登場し始めると、なんもわからん状態になってしまい、LLVMの基礎知識のなさを実感し、一旦LLVM Tutorialを中断して、LLVMの基礎を勉強することにしました。
前置きが長くなりましたが、このような背景があり、LLVMの基礎を見につけるためにLLVM IRを使ってBrainFuckコンパイラを作ってみることにしました。
開発環境
$llvm-config --version 10.0.0 $clang++ --version clang version 10.0.0-4ubuntu1 Target: x86_64-pc-linux-gnu Thread model: posix InstalledDir: /usr/bin
main関数とcharを格納するメモリ領域の確保
早速、コンパイラ作りに入っていきます。
今回作成するのは、標準入力からBrainFuckソースコードを受け取り、標準出力にそのBrainFuckソースコードに対応するLLVM IRを出力するC++プログラムです。
作業は以下の流れで進めていきます。
1. LLVM IRでやりたい処理をC++で書く
2. 1.で書いたC++プログラムをLLVM IRにコンパイルする
3. 2.で生成したLLVM IRを生成するC++プログラムを書く
まず、main関数の作成とcharを格納するメモリ領域確保の処理についてです。
1. LLVM IRでやりたい処理をC++で書く
C++でmian関数を作成し、その中にメモリ領域を確保するコードを書きます。
int main() { unsigned char array[30000] = {0}; unsigned char* arrayPtr = array; return 0; }
2. 1.で書いたC++プログラムをLLVM IRにコンパイルする
コマンドclang++ -S -emit-llvm main.cppで先程書いたプログラムをコンパイルし、LLVM IRを生成します。
生成したLLVM IRから不要な箇所を削ると以下のようになります。
define i32 @main() {
%1 = alloca i32, align 4
%2 = alloca [30000 x i8], align 16
%3 = alloca i8*, align 8
store i32 0, i32* %1, align 4
%4 = bitcast [30000 x i8]* %2 to i8*
call void @llvm.memset.p0i8.i64(i8* align 16 %4, i8 0, i64 30000, i1 false)
%5 = getelementptr inbounds [30000 x i8], [30000 x i8]* %2, i64 0, i64 0
store i8* %5, i8** %3, align 8
ret i32 0
}
declare void @llvm.memset.p0i8.i64(i8* , i8, i64, i1)
alloca, bitcast, getelemetptr, storeなどの命令がありますが、これらはLLVM Language Reference Manual — LLVM 10 documentationで意味等を確認することができます。
3. 2.で生成したLLVM IRを生成するC++プログラムを書く
標準出力に先程作成したLLVM IRを出力するプログラムを書きます。
ここでは、%1 = alloca i32, align 4、store i32 0, i32* %1, align 4の行は（多分）不要なので削除しました。
int index = 4; void emit_header() { std::cout << "define i32 @main() {" << std::endl; std::cout << " %1 = alloca [30000 x i8], align 16" << std::endl; std::cout << " %2 = alloca i8*, align 8" << std::endl; std::cout << " %3 = bitcast [30000 x i8]* %1 to i8*" << std::endl; std::cout << " store i8* %3, i8** %2, align 8" << std::endl; } void emit_footer() { std::cout << " ret i32 0" << std::endl; std::cout << "}" << std::endl; std::cout << "declare void @llvm.memset.p0i8.i64(i8*, i8, i64, i1)" << std::endl; } int main() { emit_header(); emit_footer(); return 0; }
実行してみる
以下のコマンドで実行できます。
$clang++ main.cpp $./a.out > main.ll $lli main.ll
今の段階では何も起きないですが、エラーにならずにプログラムが実行できることを確認します。
ちなみに、以下のように実行することもできます。
$clang++ main.cpp $./a.out > lli
「>」「<」「+」「ー」「.」「,」命令の実装
ここからはBrainfuckの命令を実装していきます。
まず、LLVM IRでやりたい処理をC++で書き、
次に、コマンドclang++ -S -emit-llvm main.cppを実行し、LLVM IRにコンパイルし、
最後に、LLVM IRを見ながらC++のプログラムを作成していきます。
#include <iostream> int main() { unsigned char array[30000] = {0}; unsigned char* arrayPtr = array; // > ポインタをインクリメント ++arrayPtr; // < ポインタをデクリメント --arrayPtr; // + ポインタの値をインクリメント ++*arrayPtr; // - ポインタの値をデクリメント --*arrayPtr; // , 入力から1バイト読み込んで、ポインタが指す値に代入 *arrayPtr = std::getchar(); // . ポインタの値を出力 std::putchar(*arrayPtr); return 0; }
「>」「<」ポインタのインクリメント・デクリメント
LLVM IRでは、ポインタのインクリメント・デクリメントは以下のようになっています。
%6 = load i8*, i8** %3, align 8 %7 = getelementptr inbounds i8, i8* %6, i32 1 store i8* %7, i8** %3, align 8 %8 = load i8*, i8** %3, align 8 %9 = getelementptr inbounds i8, i8* %8, i32 -1 store i8* %9, i8** %3, align 8
インクリメントとデクリメントは、getelementptrの第3引数が違うだけなので一つの関数にまとめました。
void emit_add_ptr(int diff) { std::cout << " %" << index << " = load i8*, i8** %2, align 8" << std::endl; std::cout << " %" << index + 1 << " = getelementptr inbounds i8, i8* %" << index << ", i32 " << diff << std::endl; std::cout << " store i8* %" << index + 1 << ", i8** %2, align 8" << std::endl; index += 2; }
「+」「-」値のインクリメント・デクリメント
LLVM IRでは、値のインクリメント・デクリメントは以下のようになっています。
%10 = load i8*, i8** %3, align 8 %11 = load i8, i8* %10, align 1 %12 = add i8 %11, 1 store i8 %12, i8* %10, align 1 %13 = load i8*, i8** %3, align 8 %14 = load i8, i8* %13, align 1 %15 = add i8 %14, -1 store i8 %15, i8* %13, align 1
インクリメントとデクリメントは、addの第2引数が違うだけなので一つの関数にまとめました。
void emit_add(int diff) { std::cout << " %" << index << " = load i8*, i8** %2, align 8" << std::endl; std::cout << " %" << index + 1 << " = load i8, i8* %" << index << ", align 1" << std::endl; std::cout << " %" << index + 2 << " = add i8 %" << index + 1 << ", " << diff << std::endl; std::cout << " store i8 %" << index + 2 << ", i8* %" << index << ", align 1" << std::endl; index += 3; }
「.」ポインタの値の出力
LLVM IRでは、ポインタの値の出力は以下のようになっています。
%16 = call i32 @getchar() %17 = trunc i32 %16 to i8 %18 = load i8*, i8** %3, align 8 store i8 %17, i8* %18, align 1
LLVM IRのmain関数の外で、putcharを宣言する必要があるため、emit_footerメソッドにdeclare i32 @putchar(i32)を追加します。
void emit_put() { std::cout << " %" << index << " = load i8*, i8** %2, align 8" << std::endl; std::cout << " %" << index + 1 << " = load i8, i8* %" << index << ", align 1" << std::endl; std::cout << " %" << index + 2 << " = sext i8 %" << index + 1 << " to i32" << std::endl; std::cout << " %" << index + 3 << " = call i32 @putchar(i32 %" << index + 2 << ")" << std::endl; index += 4; } void emit_footer() { std::cout << " ret i32 0" << std::endl; std::cout << "}" << std::endl; std::cout << "declare void @llvm.memset.p0i8.i64(i8*, i8, i64, i1)" << std::endl; std::cout << "declare i32 @putchar(i32)" << std::endl; }
「,」入力から1バイト読み込んで、ポインタが指す値に代入
LLVM IRでは、入力から1バイト読み込んで、ポインタが指す値に代入は以下のようになっています。
%16 = call i32 @getchar() %17 = trunc i32 %16 to i8 %18 = load i8*, i8** %3, align 8 store i8 %17, i8* %18, align 1
LLVM IRのmain関数の外で、putcharを宣言する必要があるため、emit_footerメソッドにdeclare i32 @getchar()を追加します。
void emit_get() { std::cout << " %" << index << " = call i32 @getchar()" << std::endl; std::cout << " %" << index + 1 << " = trunc i32 %" << index << " to i8" << std::endl; std::cout << " %" << index + 2 << "= load i8*, i8** %2, align 8" << std::endl; std::cout << " store i8 %" << index + 1 << ", i8* %" << index + 2 << ", align 1" << std::endl; index += 3; } void emit_footer() { std::cout << " ret i32 0" << std::endl; std::cout << "}" << std::endl; std::cout << "declare void @llvm.memset.p0i8.i64(i8*, i8, i64, i1)" << std::endl; std::cout << "declare i32 @getchar()" << std::endl; std::cout << "declare i32 @putchar(i32)" << std::endl; }
実行してみる
ここまで作成したプログラムを実行するために、C++のmain関数に各関数を呼び出す処理を追加します。
int main() { emit_header(); while ((c = getchar()) != EOF) { switch (c) { case '>': emit_add_ptr(1); break; case '<': emit_add_ptr(-1); break; case '+': emit_add(1); break; case '-': emit_add(-1); break; case '.': emit_put(); break; case ',': emit_get(); break; } } emit_footer(); return 0; }
以下のコマンドで実行すると、Hello world!出力されます。
$clang++ main.cpp $echo "++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.+++++++++++++++++++++++++++++.+++++++..+++.>++++++++++++++++++++++++++++++++.<++++++++.--------.+++.------.--------.>+." | ./a.out | lli Hello world!
「[」「]」命令の実装
「[」命令（ポインタの指す値が0なら、後の]までジャンプ）、「]」命令（ ポインタの指す値が0でなければ、前の[までジャンプ）は、while文の処理です。 C++で「[」命令、「]」命令に相当する処理を書いて、LLVM IRにコンパイルします。
#include <iostream> int main() { unsigned char array[30000] = {0}; unsigned char *arrayPtr = array; ++*arrayPtr; ++*arrayPtr; ++*arrayPtr; ++*arrayPtr; while (*arrayPtr == 0) { --*arrayPtr; } ++*arrayPtr; ++*arrayPtr; ++*arrayPtr; ++*arrayPtr; return 0; }
LLVM IRは以下のようになります。
define i32 @main() {
; -----省略-----
%15 = load i8*, i8** %3, align 8
%16 = load i8, i8* %15, align 1
%17 = add i8 %16, 1
store i8 %17, i8* %15, align 1
br label %18
18: ; preds = %23, %0
%19 = load i8*, i8** %3, align 8
%20 = load i8, i8* %19, align 1
%21 = zext i8 %20 to i32
%22 = icmp eq i32 %21, 0
br i1 %22, label %23, label %27
23: ; preds = %18
%24 = load i8*, i8** %3, align 8
%25 = load i8, i8* %24, align 1
%26 = add i8 %25, -1
store i8 %26, i8* %24, align 1
br label %18
27: ; preds = %18
%28 = load i8*, i8** %3, align 8
%29 = load i8, i8* %28, align 1
%30 = add i8 %29, 1
store i8 %30, i8* %28, align 1
; -----省略-----
ret i32 0
}
このLLVM IRを出力するC++プログラムは以下のようになります。
void emit_while_start(int while_index) { std::cout << " br label %while_start" << while_index << std::endl; std::cout << "while_start" << while_index << ":" << std::endl; std::cout << " %" << index << " = load i8*, i8** %2, align 8" << std::endl; std::cout << " %" << index + 1 << " = load i8, i8* %" << index << ", align 1" << std::endl; std::cout << " %" << index + 2 << " = icmp ne i8 %" << index + 1 << ", 0" << std::endl; std::cout << " br i1 %" << index + 2 << ", label %while_body" << while_index << ", label %while_end" << while_index << std::endl; std::cout << "while_body" << while_index << ":" << std::endl; index += 3; } void emit_while_end(int while_index) { std::cout << " br label %while_start" << while_index << std::endl; std::cout << "while_end" << while_index << ":" << std::endl; }
実行してみる
main関数に「[」命令、「]」命令の処理を追加します。
int main() { emit_header(); char c; int while_index = 0; int while_indices[1000]; int *while_index_ptr = while_indices; while ((c = getchar()) != EOF) { switch (c) { case '>': emit_add_ptr(1); break; case '<': emit_add_ptr(-1); break; case '+': emit_add(1); break; case '-': emit_add(-1); break; case '.': emit_put(); break; case ',': emit_get(); break; case '[': emit_while_start(*while_index_ptr++ = while_index++); break; case ']': emit_while_end(*--while_index_ptr); break; } } emit_footer(); return 0; }
以下のコマンドで実行すると、Hello world!出力されます。
$clang++ main.cpp $echo "+++++++++[>++++++++>+++++++++++>+++>+<<<<-]>.>++.+++++++..+++.>+++++.<<+++++++++++++++.>.+++.------.--------.>+.>+." | ./a.out | lli Hello world!
全コード
#include <iostream> int index = 4; void emit_header() { std::cout << "define i32 @main() {" << std::endl; std::cout << " %1 = alloca [30000 x i8], align 16" << std::endl; std::cout << " %2 = alloca i8*, align 8" << std::endl; std::cout << " %3 = bitcast [30000 x i8]* %1 to i8*" << std::endl; std::cout << " store i8* %3, i8** %2, align 8" << std::endl; } void emit_add_ptr(int diff) { std::cout << " %" << index << " = load i8*, i8** %2, align 8" << std::endl; std::cout << " %" << index + 1 << " = getelementptr inbounds i8, i8* %" << index << ", i32 " << diff << std::endl; std::cout << " store i8* %" << index + 1 << ", i8** %2, align 8" << std::endl; index += 2; } void emit_add(int diff) { std::cout << " %" << index << " = load i8*, i8** %2, align 8" << std::endl; std::cout << " %" << index + 1 << " = load i8, i8* %" << index << ", align 1" << std::endl; std::cout << " %" << index + 2 << " = add i8 %" << index + 1 << ", " << diff << std::endl; std::cout << " store i8 %" << index + 2 << ", i8* %" << index << ", align 1" << std::endl; index += 3; } void emit_put() { std::cout << " %" << index << " = load i8*, i8** %2, align 8" << std::endl; std::cout << " %" << index + 1 << " = load i8, i8* %" << index << ", align 1" << std::endl; std::cout << " %" << index + 2 << " = sext i8 %" << index + 1 << " to i32" << std::endl; std::cout << " %" << index + 3 << " = call i32 @putchar(i32 %" << index + 2 << ")" << std::endl; index += 4; } void emit_get() { std::cout << " %" << index << " = call i32 @getchar()" << std::endl; std::cout << " %" << index + 1 << " = trunc i32 %" << index << " to i8" << std::endl; std::cout << " %" << index + 2 << "= load i8*, i8** %2, align 8" << std::endl; std::cout << " store i8 %" << index + 1 << ", i8* %" << index + 2 << ", align 1" << std::endl; index += 3; } void emit_while_start(int while_index) { std::cout << " br label %while_start" << while_index << std::endl; std::cout << "while_start" << while_index << ":" << std::endl; std::cout << " %" << index << " = load i8*, i8** %2, align 8" << std::endl; std::cout << " %" << index + 1 << " = load i8, i8* %" << index << ", align 1" << std::endl; std::cout << " %" << index + 2 << " = icmp ne i8 %" << index + 1 << ", 0" << std::endl; std::cout << " br i1 %" << index + 2 << ", label %while_body" << while_index << ", label %while_end" << while_index << std::endl; std::cout << "while_body" << while_index << ":" << std::endl; index += 3; } void emit_while_end(int while_index) { std::cout << " br label %while_start" << while_index << std::endl; std::cout << "while_end" << while_index << ":" << std::endl; } void emit_footer() { std::cout << " ret i32 0" << std::endl; std::cout << "}" << std::endl; std::cout << "declare void @llvm.memset.p0i8.i64(i8*, i8, i64, i1)" << std::endl; std::cout << "declare i32 @getchar()" << std::endl; std::cout << "declare i32 @putchar(i32)" << std::endl; } int main() { emit_header(); char c; int while_index = 0; int while_indices[1000]; int *while_index_ptr = while_indices; while ((c = getchar()) != EOF) { switch (c) { case '>': emit_add_ptr(1); break; case '<': emit_add_ptr(-1); break; case '+': emit_add(1); break; case '-': emit_add(-1); break; case '.': emit_put(); break; case ',': emit_get(); break; case '[': emit_while_start(*while_index_ptr++ = while_index++); break; case ']': emit_while_end(*--while_index_ptr); break; } } emit_footer(); return 0; }
