ELVMのLLVM IRバックエンドをつくった

LLVMはよく知られてるコンパイラ基盤であり, 中間表現としてLLVM IRを持っている. 様々なところでこのLLVM IRが使われているが, 今まで触ってこなかったということもあり, 今回LLVM IRで何かしら遊んでみようと思っていた.

itchyny.hatenablog.com

最近になって,上記のような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

https://github.com/shinh/elvm

http://shinh.skr.jp/slide/elvm/000.html

http://shinh.skr.jp/slide/llel/000.html

http://llvm.org/docs/LangRef.html

http://hak7a3.hatenablog.com/entry/2016/11/13/153418

http://qiita.com/Hiroki_M/items/89975a9e8205ced3603f