Edited at

こわくないLLVM入門!


対象読者


  • LLVMを勉強し始めたけど何からして良いのかわからない方

  • アセンブリがちょっとわかる


目標


  • LLVMの基本的な文法がわかるようになる


環境


  • Mac Mojave 10.14.6

  • LLVM 8.0.0

  • clang 8.0.0 (trunk 348837)


LLVMってなに...?

コンパイラは通常フロントエンド、ミドルエンド、バックエンドに分けられ、各プロセスで様々な処理をしています。特にミドルエンド、バックエンドでは中間言語や各アーキテクチャに対するたくさんの最適化を施さなければなりません。この最適化を預けてフロントエンドだけを考えればコンパイラが作れるというものがLLVMです。LLVMは強力な型システムや厳密な制約を持っていて、これにより高度な最適化技術は実現します。更にLLVMはJITを作る事ができます。JITは通常実装するのが大変ですが、LLVMを使えば楽に実装できます。更に更に他の言語でコンパイルされたLLVMの言語とリンクする事ができます。だから自分で作った言語でC言語の関数を使うことができます!


とりあえずみてみよう!


Hello, world!

エディタを開いて下のソースコードをコピペしてください。何もせずに0を返して終了するプログラムです。


helloworld.c

#include <stdio.h>


int main(int argc, char **argv) {
printf("Hello, world!\n");
return 0;
}

このファイルと同じ階層で下のコマンドを打ってください。

$ clang -S -emit-llvm -O3 helloworld.c

するとhelloworld.llというLLVMの言語で書かれたファイルが出てきます。そしてこれをllcというLLVMの言語からアセンブリのコンパイラを使い、コンパイルすると...

$ llc helloworld.ll

$ clang helloworld.s -o helloworld
$ ./helloworld
Hello, world!

実行できました!

このhelloworld.llを開いてみると...


helloworld.ll

; ModuleID = 'helloworld.c'

source_filename = "helloworld.c"
target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-apple-macosx10.14.0"

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

; Function Attrs: nounwind ssp uwtable
define i32 @main(i32 %argc, i8** nocapture readnone %argv) local_unnamed_addr #0 {
entry:
%puts = tail call i32 @puts(i8* getelementptr inbounds ([14 x i8], [14 x i8]* @str, i64 0, i64 0))
ret i32 0
}

; Function Attrs: nounwind
declare i32 @puts(i8* nocapture readonly) local_unnamed_addr #1

attributes #0 = { nounwind ssp uwtable "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "min-legal-vector-width"="0" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="penryn" "target-features"="+cx16,+fxsr,+mmx,+sahf,+sse,+sse2,+sse3,+sse4.1,+ssse3,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
attributes #1 = { nounwind }

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

!0 = !{i32 1, !"wchar_size", i32 4}
!1 = !{i32 7, !"PIC Level", i32 2}
!2 = !{!"clang version 8.0.0 (trunk 348837)"}


ウギャア!!何これ、でかい...実行に重要な部分だけを取り出してみます。


helloworld.ll

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

define i32 @main(i32 %argc, i8** %argv) {
entry:
%puts = tail call i32 @puts(i8* getelementptr inbounds ([14 x i8], [14 x i8]* @str, i64 0, i64 0))
ret i32 0
}

declare i32 @puts(i8* nocapture readonly) local_unnamed_addr #1


だいぶスッキリしました!これがLLVMの言語、LLVM IRというものです。

...と言われても全然さっぱりなので何が書かれているのか一つ一つ説明していきます。


LLVM IRでの大まかな区分

その前に、LLVM IRにはModule, Funciton, BasicBlock, Instruction の4段階の区分があります。

それぞれは曖昧ですが用途が決まっています。


  • Module はソースコードなどの大きな枠組でそれらでリンクが出来るもの。Funcion を複数持つ。

  • Function はLLVM IR内での関数でC++の関数と同じ。BasicBlock を複数持つ。

  • BasicBlock はラベルごとで分けられる小さな枠組。Instruction を複数持つ。

  • Instruction はLLVM IR内での1つの命令。

これらは言語を作っていく際によく出てきます。


LLVM IR解説


関数定義

define i32 @main(i32 %argc, i8** %argv) {

...
}

これは関数定義です。引数の%argc,%argvはレジスタです。LLVMではSSA形式という形式の中間言語の為、型を持ったレジスタをいくらでも定義する事が出来ます。int main(int argc, char **argv)と対応しています。

ここでLLVM IRの型は主に下記のようなものがあります。


LLVMでの型


  • 整数型


    • iにビット幅を指定して、i1とかi7とかi32とかi64とか最大で2^23-1(だいたい800万!)まで指定できます。



  • 浮動小数点型


    • float, doubleなど。



  • ポインタ型


    • C言語と同じように*を付けます。



  • aggregateな型


    • 配列やベクター、構造体があり,それぞれ[サイズx型], <サイズx型>, {型, 型, ...}と書きます。



  • 他にはvoid型、関数型、ラベル型、トークン型、Metadata型があります。

ちなみにcharは8ビットの型なのでi8、同じようにboolもi1です。@や%は変数や関数の前置記号として必ず付けます。それぞれ、グローバルなもの、ローカルなものという意味があります。


ちなみにLLVMにはunsigned intは存在しません。じゃどうやって使うんだよ!と思いますが、演算するときにこれはunsignedですよと指定する事で解決しています。なんで無いんだろう?と思ったらLLVM Type System Changesを参照してください。



ラベル・コメント

entry:

; なんちゃら

ラベルです。ラベルはアセンブリと同じように他のアドレスからジャンプ命令でラベルのアドレスへジャンプしてそのアドレスから処理する事が出来ます。

頭文字に';'があるとコメントになります。


文字列

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

...
%puts = tail call i32 @puts(i8* getelementptr inbounds ([14 x i8], [14 x i8]* @str, i64 0, i64 0))
...
declare i32 @puts(i8* nocapture readonly) local_unnamed_addr #1

最初に@strはサイズ14のi8の配列でグローバル変数を定義しています。call命令で@puts関数を呼び出してます。tailは末尾呼び出し最適化をする時に使います。末尾呼び出し最適化は少し難しいので解説しません。

そしてputs関数の引数のi8* getelementptr inbounds ([14 x i8], [14 x i8]* @str, i64 0, i64 0)に注目して頂きたいのですが、これはGetElementPtr(GEP)と呼ばれるものです。

これはよく誤解されたりするため公式の専用の解説ページまであります。

そして後にcall命令で関数宣言される@puts関数がこのアドレスを引数として呼び出しています。

そして最後にret命令で関数が返って終わります。


GetElementPtr(GEP)

GEPは配列や構造体などのsubelementのアドレスを計算します。

公式サイトの例を見てみると

struct munger_struct {

int f1;
int f2;
};
void munge(struct munger_struct *P) {
P[0].f1 = P[1].f1 + P[2].f2;
}
...
munger_struct Array[3];
...
munge(Array);

これをclangでコンパイルしてmunger_structとmunge関数を見てみます。

%struct.munger_struct = type { i32, i32 }

void %munge(%struct.munger_struct* %P) {
entry:
%tmp = getelementptr %struct.munger_struct, %struct.munger_struct* %P, i32 1, i32 0
%tmp = load i32* %tmp
%tmp6 = getelementptr %struct.munger_struct, %struct.munger_struct* %P, i32 2, i32 1
%tmp7 = load i32* %tmp6
%tmp8 = add i32 %tmp7, %tmp
%tmp9 = getelementptr %struct.munger_struct, %struct.munger_struct* %P, i32 0, i32 0
store i32 %tmp8, i32* %tmp9
ret void
}

getelementptrはある変数のアドレスを計算するもので、3つ以上のオペランドから構成されています。

getelementptr <1st_op>, <2nd_op>, <3rd_op>*

それぞれ

1つ目: 元の型

2つ目: ベースとなるアドレス

3つ目以降: 配列や構造体などのインデックス

となっています。

LLVM IRとC言語を対応してみてみると...


LLVM IR

    %tmp9 = getelementptr %struct.munger_struct, %struct.munger_struct* %P, i32 0, i32 0

%tmp = getelementptr %struct.munger_struct, %struct.munger_struct* %P, i32 1, i32 0
%tmp6 = getelementptr %struct.munger_struct, %struct.munger_struct* %P, i32 2, i32 1


C言語

    tmp9 = &P[0].f1

tmp = &P[1].f1
tmp6 = &P[2].f2

それぞれ型の情報とインデックスから計算出来ます。例えば、i32の配列であれば32 * インデックス数をベースのアドレスに足してアドレスを計算します。すると

    %puts = tail call i32 @puts(i8* getelementptr inbounds ([14 x i8], [14 x i8]* @str, i64 0, i64 0))

これはC言語で書くと&str[0][0]で、strの開始アドレスに指定されていると分かります。ちなみにこのinboundsというパラメータは配列などに範囲外のアドレスを指定してない事を示しています。


条件分岐

int branch(int cond) {

int i = -1;
if (cond == 0) {
i = 0;
}else{
i = 1;
}
return i;
}

最適化無しでコンパイルします。

define i32 @branch(i32 %cond) {

entry:
%cond.addr = alloca i32, align 4
%i = alloca i32, align 4
store i32 %cond, i32* %cond.addr, align 4
store i32 -1, i32* %i, align 4
%0 = load i32, i32* %cond.addr, align 4
%cmp = icmp eq i32 %0, 0
br i1 %cmp, label %if.then, label %if.else

if.then: ; preds = %entry
store i32 0, i32* %i, align 4
br label %if.end

if.else: ; preds = %entry
store i32 1, i32* %i, align 4
br label %if.end

if.end: ; preds = %if.else, %if.then
%1 = load i32, i32* %i, align 4
ret i32 %1
}

icmp命令はcmp命令とbr命令はjmp系と対応しています。icmpは整数内で比較でき、それと対応してfcmpは小数内で比較できます。


変数のための命令

alloca, store, load命令は変数を扱う為に必要です。

    %<ptr> = alloca <type> (, align <alignment>)

store <type> <value>, <ptr_type> %<ptr>
%val = load <type>, <ptr_type> %<ptr>

alloca命令はtypeのbit幅分メモリ確保し、そのアドレスを返します。

store命令はアドレスのメモリへ値を書き込みます。

load命令はアドレスを読み込む時に使います。

alignはアラインメントを指定し、指定しなければ最初に省略したところにあるデータレイアウトを参照します。


その他

最初に省略したものは上下に2つあります。まず上では

; ModuleID = 'helloworld.c'

source_filename = "helloworld.c"
target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-apple-macosx10.14.0"

1~2行目はソースコード名。これは特に問題ないですね。3行目はデータレイアウト、これは型別のアラインメントやエンディアンなどを定義しています。4行目はtarget-tripleというものでアーキテクチャやOSなどの情報が載っています。もちろんここは環境によって異なります。

attributes #0 = { nounwind ssp uwtable "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "min-legal-vector-width"="0" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="penryn" "target-features"="+cx16,+fxsr,+mmx,+sahf,+sse,+sse2,+sse3,+sse4.1,+ssse3,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }

attributes #1 = { nounwind }

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

!0 = !{i32 1, !"wchar_size", i32 4}
!1 = !{i32 7, !"PIC Level", i32 2}
!2 = !{!"clang version 8.0.0 (trunk 348837)"}

1~2行目は属性です。属性は変数や関数に埋め込んでコンパイルの設定や動的なエラーを起こす事などが出来ます。前置記号として'#'を使います。例えばnounwindは関数が例外を発生させない事、sspはcanaryを生成する事を示しています。

4~9行目はmetadataです。metadataはソースコードに埋め込んでデバッグ情報や言語固有の最適化で使います。前置記号として'!'を使います。


これから

これくらいの知識でも大体の機能(ループや構造体、タプル、オブジェクト指向や関数型言語まで...は言い過ぎでもないけど)が実装出来ると思います。とりあえず、一通り簡単な言語を作ってみると良いと思います。簡単にLLVM IRを出力してくれるライブラリはC++のllvmやRustのllvm_sysやinkwell他人のコードや公式リファレンスを読みつつ、分からないところがあればGoogleに投げればLLVM Doxygenがあるので進められます。


参考文献


公式ドキュメント


書籍



  • きつねさんでもわかるLLVM


    • LLVMの情報と言語処理系の解説、最適な作り方がとても詳しく載っていました。(バージョンが少し違っていて上手く動かない部分もあります)




記事