Ruby -> Julia -> LLVM IR -> たのしい

先月のRubyConfのLTで[A PoC-ish Trick: LLVM IR Generation with Ruby](https://speakerdeck.com/remore/a-poc-ish-trick-llvm-ir-generation-with-ruby)という題で発表してきた小ネタです。

## TL;DR

1. RubyのコードをJuliaに変換する[Julializer](https://github.com/remore/julializer)というTranspilerを作った
2. Juliaでは`code_llvm`や`code_native`等の組み込み関数でLLVM IRやアセンブリコードを簡単に吐き出せる
3. 1と2から、Rubyのコードを書くとLLVM IRやアセンブリコードを簡単に吐き出せる 

#### Disclaimer

 - Julializerは[Fixnum, Floatなどごく一部のClassのみサポートしているに過ぎない](https://github.com/remore/julializer#supported-classes-and-syntax)ので、Rubyの機能のごくごく一部しか変換できません

## Demo

最も単純な例として、Rubyの`2+3`（整数同士の加算）というプログラムを変換してみます。LLVM IRの結果として作成されている関数`julia_+_21483`の引数として、`i64`という整数型の引数が取られていることに着目してください。

```bash
bash-3.2# echo "2+3" | julializer # Ruby->Julia
2+3;
bash-3.2# echo "2+3" | julializer | sed 's/^/@code_llvm /' | julia # Ruby->Julia->LLVM IR

define i64 @"julia_+_21483"(i64, i64) {
top:
  %2 = add i64 %1, %0
  ret i64 %2
}
```

次にRubyで`2.3+3`（浮動小数点数と整数の加算）と表現されるプログラムを変換してみると、以下のようにJulia->LLVM IRの段階で型推論が効いて`julia_+_21484`の引数として`(double, i64)`のように浮動小数点型が宣言されていることが確認できます。

```bash
bash-3.2# echo "2.3+3" | julializer # Ruby->Julia
2.3+3;
bash-3.2# echo "2.3+3" | julializer | sed 's/^/@code_llvm /' | julia # Ruby->Julia->LLVM IR

define double @"julia_+_21484"(double, i64) {
top:
  %2 = sitofp i64 %1 to double
  %3 = fadd double %0, %2
  ret double %3
}
```

これを使って、for文を使ったごく単純な算術演算プログラムであれば以下のようにRubyからJuliaを経由してLLVMの表現を作ることができます。以下は、LLVM IRの替わりにアセンブリコードの出力をしてみた例です。

```bash
bash-3.2# echo "
> def loop(list)
>   for i in 0.5.to_i..list.size-1
>     list[i] = (i-list.size/2).abs
>   end
> end
> " | julializer # Ruby->Julia
function loop(list);for i::Int64 = trunc(Int64,parse(string(0.5))):size(list)[1]-1;list[i+1]=abs((i-size(list)[1]/2));;end;;;end;;
bash-3.2# echo "
> def loop(list)
>   for i in 0.5.to_i..list.size-1
>     list[i] = (i-list.size/2).abs
>   end
> end
> " | julializer | sed 's/$/code_native(loop, (Array{Int64,1},))/' | julia # Ruby->Julia->Machine Code
	.section	__TEXT,__text,regular,pure_instructions
Filename: none
Source line: 1
	pushq	%rbp
	movq	%rsp, %rbp
	pushq	%r15
	pushq	%r14
	pushq	%r13
	pushq	%r12
	pushq	%rbx
	subq	$88, %rsp
	movq	%rdi, %r15
Source line: 1
	movq	%r15, -120(%rbp)
	movq	$14, -112(%rbp)
	movabsq	$jl_pgcstack, %rax
	movq	(%rax), %rcx
	movq	%rcx, -104(%rbp)
	leaq	-112(%rbp), %rcx
	movq	%rcx, (%rax)
	movq	$0, -96(%rbp)
	movq	$0, -88(%rbp)
	movq	$0, -80(%rbp)
	leaq	-56(%rbp), %rbx
Source line: 1
	movabsq	$print_to_string, %rax
	movabsq	$4585538608, %rcx       ## imm = 0x11151C430
	movabsq	$4554689512, %rdx       ## imm = 0x10F7B0BE8
	xorpd	%xmm0, %xmm0
Source line: 1
	movq	$0, -72(%rbp)
	movq	$0, -64(%rbp)
	movupd	%xmm0, -56(%rbp)
Source line: 1
	movq	(%rdx), %rdx
	movq	%rdx, -64(%rbp)
	movq	%rcx, -56(%rbp)
	movabsq	$4574850160, %rdi       ## imm = 0x110AEAC70
	movq	%rbx, %rsi
	movl	$1, %edx
	callq	*%rax
	movabsq	$jl_apply_generic, %r14
	movq	%rax, -56(%rbp)
	movabsq	$4582578128, %rdi       ## imm = 0x1112497D0
	movq	%rbx, %rsi
	movl	$1, %edx
	callq	*%r14
Source line: 1
	leaq	-64(%rbp), %rbx
Source line: 1
	movq	%rax, -56(%rbp)
	movabsq	$4578677360, %rdi       ## imm = 0x110E91270
	movq	%rbx, %rsi
	movl	$2, %edx
	callq	*%r14
	movabsq	$jl_box_int64, %rcx
	movq	%rax, -88(%rbp)
	movq	24(%r15), %rdi
	movq	%rbx, %r15
	movq	%rax, -64(%rbp)
	decq	%rdi
	callq	*%rcx
	movq	%rax, -56(%rbp)
	movabsq	$4573878480, %rdi       ## imm = 0x1109FD8D0
	movq	%r15, %rsi
	movl	$2, %edx
	callq	*%r14
	movq	%rax, %rbx
	movq	%rbx, -80(%rbp)
	movq	%rbx, -64(%rbp)
	movabsq	$4590321552, %rdi       ## imm = 0x1119ABF90
	movq	%r15, %rsi
	movl	$1, %edx
	callq	*%r14
	movq	%rax, -96(%rbp)
	movq	%rbx, -64(%rbp)
	movq	-96(%rbp), %rax
	movq	%rax, -56(%rbp)
	movabsq	$4590048656, %rdi       ## imm = 0x111969590
	movq	%r15, %rsi
	movl	$2, %edx
	callq	*%r14
	movq	%rax, -64(%rbp)
	movabsq	$4576747568, %rdi       ## imm = 0x110CBA030
	movq	%r15, %rsi
	movl	$1, %edx
	callq	*%r14
	movq	-8(%rax), %rcx
	shrq	$4, %rcx
	cmpq	$284661857, %rcx        ## imm = 0x10F79861
	jne	L944
	movabsq	$jl_false, %rcx
	cmpq	(%rcx), %rax
	je	L887
	movabsq	$jl_apply_generic, %r14
	movabsq	$13161910880, %rax      ## imm = 0x31082D260
	movsd	(%rax), %xmm0
	movsd	%xmm0, -128(%rbp)
	movabsq	$jl_f_get_field, %r12
L462:	movq	%rbx, -64(%rbp)
	movq	%rbx, %r13
	movq	-96(%rbp), %rax
	movq	%rax, -56(%rbp)
	movabsq	$4583657840, %rdi       ## imm = 0x111351170
	movq	%r15, %rsi
	movl	$2, %edx
	callq	*%r14
	movq	%rax, %rbx
	movq	%rbx, -72(%rbp)
	movabsq	$4554689512, %rax       ## imm = 0x10F7B0BE8
	movq	(%rax), %rax
	movq	%rax, -64(%rbp)
	movq	%rbx, -56(%rbp)
	movabsq	$4554711168, %rax       ## imm = 0x10F7B6080
	movq	%rax, -48(%rbp)
	xorl	%edi, %edi
Source line: 1
	leaq	-56(%rbp), %rsi
	movl	$2, %edx
Source line: 1
	callq	*%r12
	movq	%rax, -56(%rbp)
	movabsq	$4591208368, %rdi       ## imm = 0x111A847B0
	movq	%r15, %rsi
	movl	$2, %edx
	callq	*%r14
	movq	-8(%rax), %rcx
	shrq	$4, %rcx
	cmpq	$284661845, %rcx        ## imm = 0x10F79855
	jne	L989
	movq	%r15, %rsi
	movq	(%rax), %r15
	movq	%rbx, -64(%rbp)
	movabsq	$4554711216, %rax       ## imm = 0x10F7B60B0
	movq	%rax, -56(%rbp)
	xorl	%edi, %edi
	movq	%rsi, %r14
	movl	$2, %edx
	callq	*%r12
	movq	%rax, -96(%rbp)
	movq	-120(%rbp), %rdi
	cmpq	8(%rdi), %r15
	jae	L1034
	cvtsi2sdq	24(%rdi), %xmm0
	divsd	-128(%rbp), %xmm0
	cvtsi2sdq	%r15, %xmm1
	addsd	%xmm0, %xmm1
	movd	%xmm1, %rax
	movabsq	$9223372036854775807, %rcx ## imm = 0x7FFFFFFFFFFFFFFF
	andq	%rcx, %rax
	movd	%rax, %xmm1
	cvttsd2si	%xmm1, %rax
	xorps	%xmm0, %xmm0
	cvtsi2sdq	%rax, %xmm0
	ucomisd	%xmm0, %xmm1
	movq	%r13, %rbx
	jne	L919
	jp	L919
	cvttsd2si	%xmm0, %rcx
	cmpq	%rcx, %rax
	jne	L919
	movq	(%rdi), %rcx
	movq	%rax, (%rcx,%r15,8)
	movq	%rbx, -64(%rbp)
	movq	-96(%rbp), %rax
	movq	%rax, -56(%rbp)
	movabsq	$4590048656, %rdi       ## imm = 0x111969590
	movq	%r14, %r15
	movq	%r15, %rsi
	movl	$2, %edx
	movabsq	$jl_apply_generic, %r14
	callq	*%r14
	movq	%rax, -64(%rbp)
	movabsq	$4576747568, %rdi       ## imm = 0x110CBA030
	movq	%r15, %rsi
	movl	$1, %edx
	callq	*%r14
	movq	%rax, -64(%rbp)
	movabsq	$4576747568, %rdi       ## imm = 0x110CBA030
	movq	%r15, %rsi
	movl	$1, %edx
	callq	*%r14
	movq	-8(%rax), %rcx
	shrq	$4, %rcx
	cmpq	$284661857, %rcx        ## imm = 0x10F79861
	jne	L1068
	movabsq	$jl_false, %rcx
	cmpq	(%rcx), %rax
	je	L462
L887:	movq	-104(%rbp), %rax
	movabsq	$jl_pgcstack, %rcx
	movq	%rax, (%rcx)
	leaq	-40(%rbp), %rsp
	popq	%rbx
	popq	%r12
	popq	%r13
	popq	%r14
	popq	%r15
	popq	%rbp
	ret
L919:	movabsq	$jl_inexact_exception, %rax
	movq	(%rax), %rdi
	movabsq	$jl_throw, %rax
	callq	*%rax
L944:	movabsq	$jl_type_error_rt, %rbx
	movabsq	$13317660823, %rdi      ## imm = 0x319CB6097
	movabsq	$13317660724, %rsi      ## imm = 0x319CB6034
	movabsq	$4554589712, %rdx       ## imm = 0x10F798610
	movq	%rax, %rcx
	callq	*%rbx
L989:	movabsq	$jl_type_error_rt, %rbx
	movabsq	$13317660823, %rdi      ## imm = 0x319CB6097
	movabsq	$13317660754, %rsi      ## imm = 0x319CB6052
	movabsq	$4554589520, %rdx       ## imm = 0x10F798550
	movq	%rax, %rcx
	callq	*%rbx
L1034:	movq	%rsp, %rax
	leaq	-16(%rax), %rsi
	movq	%rsi, %rsp
	incq	%r15
	movq	%r15, -16(%rax)
	movabsq	$jl_bounds_error_ints, %rax
	movl	$1, %edx
	callq	*%rax
L1068:	movabsq	$jl_type_error_rt, %rbx
	movabsq	$13317660823, %rdi      ## imm = 0x319CB6097
	movabsq	$13317660724, %rsi      ## imm = 0x319CB6034
	movabsq	$4554589712, %rdx       ## imm = 0x10F798610
	movq	%rax, %rcx
	callq	*%rbx
```

## まとめ

- 今のところ[word2vec.rb(Mikolovらの手法を実装したC言語のword2vecをナイーブにRubyにportingしたもの)はLLVMで表現できそう](https://speakerdeck.com/remore/how-i-made-a-pure-ruby-word2vec-program-more-than-3x-faster?slide=56)なところまでは確認
  * 但し前述のDisclaimerに記述した通り変換できるRuby上の表現が非常に限定的なため利用用途は極端に限定されます
- 型推論が存在しない世界であるRubyのコードをJuliaを経由してLLVM IRで表現することで、これまで得られなかった力がRubyにもたらされ得るという部分が個人的には面白いと思いQiitaにまとめました