Edit

yhara.jp

Recent Posts
Edit

LLVMで言語をつくる

Tech

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

記述はLLVM 3.8.1 or 3.9.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に関するページがあるのだけど、これは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

LLDB 使い方メモ

バイナリは生成できるが実行時に落ちるとき

$ lldb examples/a.sk.out -o run -o bt

最後まで実行できるが動作がおかしいとき

(lldb) breakpoint set --name lambda_1_in_toplevel
(lldb) run

参考 https://qiita.com/theefool/items/8b985ce71dcdccf26abc

トラブルシューティング

ツールごとのエラー感度の違い

  • lli, llc, llvm-dis, opt, clangなどLLVM IRを入力とするツールはいろいろあるが、「どのようなIRをエラーと見なすか」は統一されていない
  • また同じツールでも入力によって違ったりする
  • 「optに.bcを食わせた場合」が一番エラーが多く出る
    • その代わり全部のエラーを出してくれるので、他のより便利(他のは最初の１個しか教えてくれない)
    • 正常に動作するバイナリを吐ける場合でも、optがエラーを出すことがある
    • optがエラーを出さない状態を保ったほうが安全…かもしれない

error: Explicit load/store type does not match pointee type of pointer operand (Producer: 'LLVM9.0.1' Reader: 'LLVM 9.0.1')

loadかstoreの型がおかしい。が、場所を教えてくれない。困る。

.bcをllvm-disにかけても同じエラーが出るが、.llを別途生成しlliで実行すると場所がわかる場合がある。

lli: examples/a.sk.ll:1155:9: error: stored value and pointer type do not match
  store %Maybe* %result, %Void** %"expr@0"
        ^

error: instruction forward referenced with type 'xx'

「それ、前にxx型として参照されてるんですけど」というエラー。例：

/Users/yhara/Dropbox/proj/shiika % lli examples/a.sk.ll
lli: examples/a.sk.ll:996:3: error: instruction forward referenced with type '%Maybe*'
  %ifResult = phi %"Maybe::Some"* [ %result10, %"Invoke_Meta:Maybe::Some#new_end" ], [ %result22, %"Invoke_Meta:Maybe::Some#new_end23" ]
  ^

これより前で以下のように%Maybe*として扱っていたのでエラーになっていた。bitcastが必要。 %methodResult = phi %Maybe* [ %ifResult, %Ret ] …なんだけど.bcだとbitcastなしでも通るっぽい？

error: Invalid record

.bcの読み込み時に出るやつ。.bcが読めないということなのでllvm-disで見ることもできない。困る。

call命令使用時に関数の型と渡す引数が合致していないときに出るっぽい。例えば

define %Class.0* @Meta_Class_new(%"Meta:Class"* %self, %String* %"@name") {

という関数を call %Class.0* @Meta_Class_new(%Metaclass* null, %String* %sk_str1) のように呼び出したときに発生したことがある。

error: invalid use of function-local name

定数式に定数でないものを入れるとこうなった（inkwellでbuild_xxを使うべきところでconst_xxを使っていた）

opt: a.ll:20:37: error: invalid use of function-local name
  %result2 = call ptr inttoptr (i64 %result1 to ptr)(ptr %0, i64 0)

Tips、記事

More posts

Posts

(more...)

Articles

(more...)

Category

Ads

About

About the author