llvm : ハノイの塔

少し面白そうだったのでllvm(Low Level Virtual Machine)のマニュアル*1を読んでみる。
今日は、半分くらいまで読んで終了。
現時点の知識で、ハノイの塔を実装してみた。

;;; ファイル名: hanoi.ll
; printf関数に渡すフォーマット文字列
@.MSG = internal constant [10 x i8] c"%c -> %c\0A\00"

declare i32 @printf(i8*, i8, i8)

; ハノイの塔 : 再帰関数
define void @hanoi(i8 %start, i8 %tmp, i8 %dist, i32 %level) {
  %cond = icmp eq i32 %level, 0
  br i1 %cond, label %end, label %recur
recur:
  %msg = getelementptr [10 x i8]* @.MSG, i64 0, i64 0

  %level2 = sub i32 %level, 1
  call void @hanoi(i8 %start, i8 %dist, i8 %tmp, i32 %level2)
  call i32 @printf(i8* %msg, i8 %start, i8 %dist)
  call void @hanoi(i8 %tmp, i8 %start, i8 %dist, i32 %level2)
  ret void
end:
  ret void
}

; メイン関数
define i32 @main() {
  call void @hanoi(i8 65, i8 66, i8 67, i32 5)
  ret i32 0
}

実行など。

# バイトコンパイル
$ llvm-as hanoi.ll -o hanoi.bc

# 実行
$ lli hanoi.bc
A -> C
A -> B
C -> B
A -> C
B -> A
B -> C
... 以下略 ...

# ネイティブコンパイル : hanoi.sというファイルができる
$ llc hanoi.bc  

# 実行可能ファイル作成
$ gcc -o hanoi hanoi.s

# 再度実行
$ ./hanoi
A -> C
A -> B
C -> B
A -> C
B -> A
B -> C
... 以下略 ...

low levelという割には書きやすく、ほとんど(というと大げさだが)C言語と同じような感覚で書くことができた。

まだ、llvmの特徴とか、何ができるのかとかは全然分かっていないが、もう少し調べて、最終的にはこれを使ってコンパイラを実装してみても良いかもしれない、と考えている。

*1:LLVM Language Reference Manual — LLVM 3.4 documentation