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

LLVMを始めよう！ 〜 LLVM IRの基礎はclangが教えてくれた・Brainf**kコンパイラを作ってみよう 〜

最近になって，上記のようなBrainF**kを題材にLLVM IRを出力するような 記事が上がっており，こちらの記事に刺激を受け， ELVMのLLVM IRバックエンドを作成した．

じつは，以前に，Luaバックエンドを作成していた． ほとんどPythonバックエンドと同等であり，Luaを書いた経験はなかったにもかかわらず， 調べるのに使った時間を含めても2時間足らずで実装できたと記憶している．

なお，先日電気通信大学のMMA主催のDentoo.LTにおいて 本バックエンドについて発表を行なった． 本稿は発表で伝えきれなかった部分を含めた記事となっている．

今回作成したバックエンドのコードは以下．

retrage/elvm at retrage/ll

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

retrage/8cc.c.eir.ll

上記のものをopt -O3で最適化したもの

retrage/8cc.c.eir.ll.opt.ll

上記のものをllcによりWebAssemblyのアセンブリコードにしたもの

retrage/8cc.c.eir.ll.opt.s

まとめ

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