近&況

Recent Posts
Edit

LLVMで言語をつくる

LLVMで自作言語作るときのTipsなど。

記述はLLVM 3.8.1のものです。

準備

LLVMのインストール

Macならhomebrewで入る(brew install llvm)

言語バインディングを使うかどうか

LLVMはデフォルトでC++, Python, Golang, OCamlをサポートしている。これら以外の言語を使う場合は、LLVMのAPIを扱うためのバインディングがあるかを確認する。

バインディングがない場合、.llファイル(LLVM IRをテキストにしたもの)を生成し、それをlliコマンドなどで実行するという方法がある。Kareidoはこの方式である。

declare i32 @putchar(i32)

define i32 @main(){
  call i32 @putchar(i32 72)
  call i32 @putchar(i32 105)
  call i32 @putchar(i32 10)
  ret i32 0
}

上記をhello.llというファイルに保存し、lliコマンドに渡すと以下のようになる。

$ lli hello.ll
Hi

.llファイルの書き方はLangRef.htmlか、きつねさんでもわかるLLVMなどの書籍を参考のこと。

調査

C言語がどのようなIRに変換されるか調べる

適当なCのソースを以下のようにするとfoo.llができる

$ clang -S -emit-llvm foo.c

CrystalがどのようなIRを生成するか調べる

$ cat a.cr
print 123
$ crystal build --emit llvm-ir a.cr

SwiftがどのようなIRを生成するか調べる

$ cat a.swift
print(123)
$ swiftc -emit-ir a.swift > a.ll

LLVM IRについて

構造体(Structure Type)

例:x,y,zを要素に持つVector3という構造体、的なものは以下のように表現できる

%Vector3 = type{ i32, i32, i32 }

define i32 @main() {
  ; 構造体用のメモリをスタックに確保
  %reg1 = alloca %Vector3, align 4
  ; 構造体の2番目のメンバのアドレスを取得
  %reg2 = getelementptr inbounds %Vector3, %Vector3* %reg1, i32 0, i32 2
  ; そこに値(101)を書いてみる
  store i32 101, i32* %reg2, align 4
  ; それを読んでみる
  %reg3 = load i32, i32* %reg2, align 4
  ret i32 %reg3
}

関数ポインタ

LLVM IRではCなどのように関数ポインタを扱える。以下のような感じで動いた。

; 適当な関数
define i32 @func1(){
  ret i32 101
}

; 関数func1へのポインタを格納した配列があるとする
@ary = private constant [1 x i32 ()*] [i32 ()* @func1]

define i32 @main(){
  ; 配列の先頭の要素のアドレスを取得
  %reg1 = getelementptr [1 x i32 ()*], [1 x i32 ()*]* @ary, i64 0, i64 0
  ; それをloadでデリファレンスして関数ポインタを取得
  %reg2 = load i32 ()*, i32 ()** %reg1
  ; 関数ポインタ取得後は、普通にcall命令で呼び出せる
  %reg = call i32 %reg2()
  ret i32 %reg
}

GCについて

メモリ管理についてはいくつかの戦略が考えられる。

1. メモリ管理しない

Kareido程度の小さな言語仕様であればヒープを使わないのでメモリ管理については気にしなくてよい(変数はすべてスタックに置かれる)。

2. 手動でfreeする言語仕様にする

メモリを手動で管理し、GCを使わないという方法。

3. 保守的GCを使う

GCを使う場合、LLVM本体にはGCアルゴリズムが無いので、自分で実装するかboehm GCなど既存のものを組み込む必要がある。boehm GCを使うのはそんなに難しくない

ちなみにLLVMのドキュメントに(GCに関するページ)[http://llvm.org/docs/GarbageCollection.html]があるのだけど、これはexactなGCを入れたい場合の話なので、boehm GCのような保守的GCで良ければ読む必要はない。

crystal langがboehm GCを使ってるっぽい

4. exact GCを入れる

exactなGCを入れたい場合は、LLVMのGCサポート機能を使う必要がある。

5. メモリを確保するがfreeしない(一時的対応)

GCを入れるまでの一時的対応であれば、mallocはするがfreeしないという戦略が考えられる。この場合プログラムの実行中はメモリ使用率がどんどん増えていくが、小さいプログラムなら動かすことができる(確保したメモリはプログラム終了時に一括して解放される)。

例。

declare i8* @malloc(i64)

; mallocで確保したメモリのポインタを返す関数。LLVMにはvoid *がなく、i8*で代用する
define i8* @foo(){
  %reg1 = call i8* @malloc(i64 8)
  ret i8* %reg1
}

define i32 @main(){
  %reg1 = call i8* @foo()   ; メモリを確保する
  store i8 3, i8* %reg1       ; 何か書いてみる
  %reg2 = load i8, i8* %reg1   ; それを読んでみる
  %reg3 = zext i8 %reg2 to i32
  ret i32 %reg3
}

動かし方(上記をmalloc.llに保存したものとする):

$ lli malloc.ll
$ echo $?
3