ELVMのLLVM IRバックエンドをつくった
LLVMはよく知られてるコンパイラ基盤であり, 中間表現としてLLVM IRを持っている. 様々なところでこのLLVM IRが使われているが, 今まで触ってこなかったということもあり, 今回LLVM IRで何かしら遊んでみようと思っていた.
最近になって,上記のようなBrainF**kを題材にLLVM IRを出力するような 記事が上がっており,こちらの記事に刺激を受け, ELVMのLLVM IRバックエンドを作成した.
じつは,以前に,Luaバックエンドを作成していた. ほとんどPythonバックエンドと同等であり,Luaを書いた経験はなかったにもかかわらず, 調べるのに使った時間を含めても2時間足らずで実装できたと記憶している.
なお,先日電気通信大学のMMA主催のDentoo.LTにおいて 本バックエンドについて発表を行なった. 本稿は発表で伝えきれなかった部分を含めた記事となっている.
今回作成したバックエンドのコードは以下.
GitHub - retrage/elvm: EsoLangVM Compiler Infrastructure
CからELVM IRを経由してLLVM IRへ変換してみる
以下のようなCのコードを考えてみる.
#include <stdio.h> int main() { const char* p = "Hello, world!\n"; for (; *p; p++) putchar(*p); return 0; }
最初にこのCコードをELVM付属の8ccを用いて ELVM IRに変換する.
$ out/8cc -S -I. -Ilibc -Iout test/hello.c $ wc –l hello.s 12554 hello.s $ cat hello.s | head -15 .text my_div: mov D, SP add D, -1 store BP, D mov SP, D mov BP, SP sub SP, 52 .file 1 "/home/vagrant/elvm/libc/_builtin.h" .loc 1 35 0 # } .loc 1 11 0 # unsigned int r[24]; .loc 1 12 0 # unsigned int i;
生成されたhello.sは12,554行あり, その中身はELVM IRであることがわかる.
次に得られたELVM IRをelcによりCコード に変換する.
$ out/elc -c hello.s > hello.c.eir.c $ wc -l hello.c.eir.c 11290 hello.c.eir.c $ cat hello.c.eir.c | head -15 #include <stdio.h> #include <stdlib.h> unsigned int a; unsigned int b; unsigned int c; unsigned int d; unsigned int bp; unsigned int sp; unsigned int pc; unsigned int mem[1<<24]; void func0() { while (0 <= pc && pc < 512) { switch (pc) { case -1: /* dummy */
elcにより生成されたhello.c.eir.cは 11,290行あり,Cコードへ変換されていることがわかる.
ここで得られたCコード'をclangにより LLVM IRに変換し, さらにLLVM IRのインタプリタであるlliにより実行してみる.
$ clang -S -O0 -emit-llvm hello.c.eir.c hello.c.eir.c:13:11: warning: comparison of 0 <= unsigned expression is always true [-Wtautological-compare] while (0 <= pc && pc < 512) { ~ ^ ~~ 1 warning generated. $ lli hello.c.eir.ll Hello, world! $ wc -l hello.c.eir.ll 34357 hello.c.eir.ll
33,865行と行数が増えてしまっているが, ちゃんと変換されて実行できていることがわかる. なお,行数が多いのはSSA形式になっているためと考えられる.
LLVM IRバックエンドの作成
これまでで,
Cコード -(8cc)-> ELVM IR -(elc)-> Cコード' -(clang)-> LLVM IR
と変換を行なってきた.
次にclangを介さずにELVM IRから直接LLVM IRに変換することを考える. elvm/target/c.c:c_emit_instをみるとわかるが, ELVM IRの各命令は1行程度のCコードに置き換えることができる. そのため,Cコード'をclangでLLVM IRに変換した結果を見比べていけば, ELVMのLLVMバックエンドが作成できる.
なお,ELVMのバックエンドであるelcはCで書かれており, セルフホスティングできる必要があるため, LLVM IR Builderを用いることはできなさそうである.
テストケースの00exit.eirを例にどのように変換すればいいかみていく.
$ cat test/00exit.eir exit $ out/elc -c test/00exit.eir > 00exit.eir.c clang -S -O0 -emit-llvm 00exit.eir.c
ELVM IRのexitに相当する部分を見ていく. Cコード'のうち,
case 1: exit(0);
の部分となる. これは,LLVM IRでは
; <label>:13: call void @exit(i32 0) #2 unreachable
に相当する.
このように,Cコード`から置き換えをしていくことでLLVM IRのバックエンドができた. 以下,所感.
Unnamed Identityの扱い
- Unnamed Identityとは,レジスタやラベル名などで, 特別な名前がない場合に連番でつけられる識別子のことである. この識別子は少しでもずれてしまうとエラーとなる.
REGかIMMか
- ELVM IRはsrcにレジスタ(REG)か即値(IMM)を指定できる. 同一の命令でもREGとIMMで値のロードなどの部分が大きく異なる.
case文の扱い
- Cコード'では変数pcの値をswitch-caseすることで 実行する.caseはLLVM IRではlabelとなっているが, 事前にlabelのUnnamed Identityを知ることができないため, 最初にswitch文を置くことができない. このため,全てのcase文をあらかじめ記録しておき, その後ろにswitch文を置くことでこの問題を解決している.
デバッグが困難
- 最初に見たように,Hello, world!だけでも相当な長さになってしまう. このため,Cコードから生成したELVM IRでは,問題のある箇所を発見するのは非常に困難.
LLVMの恩恵を受ける
さて,LLVM IRに変換することで受けられる恩恵として次のようなものがある. * 最適化 * 他のターゲットへの変換
ここでは,得られたLLVM IRをoptにより最適化を行い, コード量と実行速度を比較する. また,他のターゲットとして,WebAssemblyへの変換を行い, ブラウザ上で実行してみる.
最適化
最初に最適化を行ない, 雑めに比較してみる.
対象とするプログラムは先ほどのHello, world!である.
最適化前
$ wc -l hello.c.eir.ll 34357 hello.c.eir.ll $ time lli hello.c.eir.ll Hello, world! real 0m0.449s user 0m0.422s sys 0m0.026s
次のようにoptを用いて最適化を行う. 多数のオプションがあるがここでは-O3を用いる.
$ opt -S -O3 -o hello.c.eir.ll.opt.ll hello.c.eir.ll
最適化後
$ wc -l hello.c.eir.ll.opt.ll 15834 hello.c.eir.ll.opt.ll $ time lli hello.c.eir.ll.opt.ll Hello, world! real 0m0.244s user 0m0.226s sys 0m0.017s
最適化により, 行数だけでみると1/2以下になり, 速度も2倍程度になっていることがわかる.
おまけ 他ターゲットへの移植
以下はやりかけの残骸である. LLVM IRから他のターゲットへの移植をしたかった. 代表的なものとして,C/C++をJSに変換するEmscriptenが有名であるが, せっかくなので,先日安定版のFirefoxでサポートされたWebAssemblyを扱う.
あらかじめWebAssemblyターゲットを有効にしたLLVMをビルドしておく.
最初に最適化したうえで,LLVM IRをアセンブリコードに変換する.
$ opt -S -O3 8cc.c.eir.ll -o 8cc.c.eir.ll.opt.ll $ llc 8cc.c.eir.ll.opt.ll -march=wasm32
次に,アセンブリコードをwastに変換する. これによりアセンブリコードはS式に変換される.
$ s2wasm 8cc.c.eir.ll.opt.s > 8cc.c.eir.ll.opt.wast << a >> [[bad mustMatch:]]: ========== .comm a,4,2 .type b,@object # @b .comm b,4,2 ========== zsh: abort s2wasm hello.c.eir.ll.opt.s > hello.c.eir.ll.opt.wast
うまく変換できなかったようである.
念のため,ELVMのCバックエンドをclnag -march=wasm3で2LLVM IRに変換してみた. この場合には同様の問題が起きなかったため, 用いたLLVM IRがwasm向けでなかったためであると推測される. あとは, wastをsexpr-wasmにより バイトコードwasmに変換し, 入出力となるJSとHTMLを書けば,WebAssemblyで書かれた8ccが動作するはずである.
なお,これまでで得られた8ccのファイルを以下に示す.
LLVM IRに変換した8cc https://gist.github.com/retrage/5ddbbc52b0aea351917462d613acd66b
上記のものをopt -O3で最適化したもの https://gist.github.com/retrage/e7f740714f0d31776d83c23fd5355a7a
上記のものをllcによりWebAssemblyのアセンブリコードにしたもの https://gist.github.com/retrage/83891ba9f9fec76a578893b4cc7abae7
まとめ
LLVM IRを少し知りたくてELVMのLLVM IRバックエンドを作成した. まだ触れていない仕様や機能が数多くあるので,触れていきたい. また,今回はoptに投げるという雑な操作のみで最適化を行なったが, コンパイラにおいて最適化を扱った記事や書籍はあまり多くない. これらについても理解できるとおもしろそうである.
参考文献
http://shinh.hatenablog.com/entry/2016/10/18/095437
http://shinh.skr.jp/slide/elvm/000.html
http://shinh.skr.jp/slide/llel/000.html
http://llvm.org/docs/LangRef.html