LLVM tailcallopt について
Ghuloum さんの "An Incremental Approach to Compiler Construction", 3.10 Proper Tail Calls の実装のための準備。以下、嘘が含まれている可能性大ですのでご注意。
まず LLVM は http://www.llvm.org/docs/CodeGenerator.html#tailcallopt にあるように、Tail call optimization をサポートしている。これが Scheme の仕様が要求している「properly tail-recursive」と完全に同じ意味かどうかは私の理解が怪しいですが、LLVM を正しく使えば properly tail-recursive が簡単に実装できる、と期待。そのためにまずは手を動かしてみる。
前準備
テスト
まず、自分自身を沢山呼ぶ関数 fn を作成し、これを基本のテスト対象とする。Scheme で書くと以下のような、無意味な関数。
(letrec ((fn (lambda (n) (if (= n 1) 1 (fn (- n 1))))) (fn 10000000000)
以下が LLVM 版。本質的なのは call i32 @fn の部分のみで、それ以外は結果を出力(printf)しているだけ。
;; simple ver. @fmt_d = internal constant [3 x i8] c"%d\00" declare i32 @printf(i8* noalias, ...) declare i32 @putchar(i32) define i32 @main () { entry: %ret = call i32 @fn(i32 100000000) %fmt = getelementptr [3 x i8 ]* @fmt_d, i64 0, i64 0 call i32 (i8*, ...)* @printf(i8* %fmt, i32 %ret) call i32 @putchar(i32 10) ret i32 0 } define i32 @fn (i32 %x) { entry: %cmp = icmp eq i32 %x, 1 br i1 %cmp, label %if_true, label %if_else if_else: %x2 = sub i32 %x, 1 %ret = call i32 @fn(i32 %x2) ret i32 %ret if_true: ret i32 1 }
上記を test.1.ll とする。test.1.ll を以下のように実行コマンドにする。
/usr/local/bin/llvm-as -f -o test.1.bc test.1.ll /usr/local/bin/llc -f -o test.1.s test.1.bc /usr/local/bin/llvm-gcc -o test.1.exe test.1.s
こうしてできた test.1.exe を実行すると、私の環境では予定どおり segmentation fault でエラーとなった。gdb から実行すると EXC_BAD_ACCESS と出力。llc に -tailcallopt を与えても同じ。これは http://www.llvm.org/docs/CodeGenerator.html#tailcallopt の最適化がされる１つ目の条件
- Caller and callee have the calling convention fastcc.
を満たしていないので当然か。
つぎに、上記の fastcc を満たす版 test.3 を作成。微妙な違いだけど、define の後に fastcc の指定があり、@fn 内部での呼び出しを tail call fastcc に変えてある。
;; fastcc ver.
@fmt_d = internal constant [3 x i8] c"%d\00"
declare i32 @printf(i8* noalias, ...)
declare i32 @putchar(i32)
define i32 @main () {
entry:
%ret = call fastcc i32 @fn(i32 100000000)
%fmt = getelementptr [3 x i8 ]* @fmt_d, i64 0, i64 0
call i32 (i8*, ...)* @printf(i8* %fmt, i32 %ret)
call i32 @putchar(i32 10)
ret i32 0
}
define fastcc i32 @fn (i32 %x) {
entry:
%cmp = icmp eq i32 %x, 1
br i1 %cmp, label %if_true, label %if_else
if_else:
%x2 = sub i32 %x, 1
%ret = tail call fastcc i32 @fn(i32 %x2)
ret i32 %ret
if_true:
ret i32 1
}
これを オプション無しの llc で .s を作り llvm-gcc で実行ファイルを作るとやはり segmentation fault 。が、ちゃんと llc -tailcallopt とすると無事エラーが出なくなった。本当に最適化されたかどうか見るため、PowerPC 用アセンブリを見てみる。
;; test 1 .globl _fn .align 4 _fn: Leh_func_begin2: mflr r0 stw r0, 8(r1) Llabel3: stwu r1, -64(r1) Llabel4: cmplwi cr0, r3, 1 beq cr0, LBB2_2 ; if_true LBB2_1: ; if_else addi r3, r3, -1 bl _fn addi r1, r1, 64 lwz r0, 8(r1) mtlr r0 blr LBB2_2: ; if_true li r3, 1 addi r1, r1, 64 lwz r0, 8(r1) mtlr r0 blr
;; test 3 .globl _fn .align 4 _fn: Leh_func_begin2: mflr r0 stw r31, 20(r1) stw r0, 8(r1) Llabel3: stwu r1, -64(r1) Llabel4: mr r31, r1 cmplwi cr0, r3, 1 bne cr0, LBB2_2 ; if_else LBB2_1: ; if_true li r3, 1 addi r1, r31, 64 lwz r0, 8(r1) lwz r31, 20(r1) mtlr r0 addi r1, r1, 64 blr LBB2_2: ; if_else addi r3, r3, -1 addi r1, r31, 64 lwz r0, 8(r1) lwz r31, 20(r1) mtlr r0 b _fn #TC_RETURNd _fn 0 Leh_func_end2:
残念ながら私の能力では PowerPCアセンブリを読めないので、 b と blr が違う、位しか言えないが、 X86 用を出力すると少し分かり良い感じ(X86 も読める訳では無いけど、、)。llc -march=x86 とすれば PowerPC 環境でも X86 用アセンブリが参照できる。
;; test 1 _fn: Leh_func_begin2: Llabel2: subl $12, %esp movl 16(%esp), %eax cmpl $1, %eax je LBB2_2 ## if_true LBB2_1: ## if_else decl %eax movl %eax, (%esp) call _fn addl $12, %esp ret LBB2_2: ## if_true movl $1, %eax addl $12, %esp ret Leh_func_end2:
;; test 3 _fn: Leh_func_begin2: Llabel2: subl $12, %esp cmpl $1, %ecx jne LBB2_2 ## if_else LBB2_1: ## if_true movl $1, %eax addl $12, %esp ret $12 LBB2_2: ## if_else decl %ecx addl $12, %esp jmp _fn # TAILCALL Leh_func_end2:
Tail call optimization によって jmp 命令に変わっている。
また、それぞれの .bc ファイルを直接 lli コマンドで実行してみたところ、以下のようになった。
- test.1.bc - -tailcallopt を付けても付けなくても Illegal instruction エラー
- test.3.bc - -tailcallopt を付けた場合のみ正常終了, 付けないと test.1.bc と同じ
まとめとして、（こうやって書いてしまうと面白くもなんともない、、）
- http://www.llvm.org/docs/CodeGenerator.html#tailcallopt の条件を全てちゃんと満たすと tail call optimization が働く
