Edited at 2019-09-09

こわくないLLVM入門！

LLVM

対象読者

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

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

目標

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

環境

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

するとreturn.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というものです。

実際のアセンブリはここです。比較してみると面白いです。

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

関数定義

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の第一引数は元の型、第二引数はベースとなるアドレス、第三引数以降はインデックスとなります。C言語とLLVM IRを対応してみてみると...（getelementptrはアドレスを計算するものなので&P[0].f1とします。）

    &P[0].f1

C言語ではmunger_structの配列のPから数えて0番目のアドレスにあるmunger_structのf1のアドレスです。対応したLLVM IRは

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

LLVM IRでは第三引数の0は%struct.munger_struct配列の0番目、第四引数の0は構造体の0番目の要素となります。

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

話を戻して、このgetelementptrは少し分かるようになったんじゃないでしょうか。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があるので進められます。

参考文献

公式ドキュメント

公式リファレンス

公式チュートリアル
- KaleidoScopeです。BasicBlockの扱いがよく書かれてあります。

LLVM Doxygen
- 自動的に生成されたページです。

書籍

きつねさんでもわかるLLVM
- LLVMの情報と言語処理系の解説、最適な作り方がとても詳しく載っていました。（バージョンが少し違っていて上手く動かない部分もありますがそれ以上に参考になります）

記事

编译器架构的王者LLVM
- KaleidoScopeよりも詳しくとても分かりやすく書かれてあって良かったです。

LLVM 6.0 で作るフロントエンドの道しるべ
- きつねさんでもわかるLLVMやKaleidoScopeのバージョンと今のバージョンで違っていて躓いていた時に助けになりました。

Anko_9801

対象読者
目標
環境
LLVMってなに...?
とりあえずみてみよう！
Hello, world!
関数定義
LLVMでの型
ラベル・コメント
文字列
GetElementPtr(GEP)
条件分岐
変数のための命令
その他
これから
参考文献
公式ドキュメント
書籍
記事