フィボナッチ数列再考
似たようなことを既に書いた気もするけど、あらためて fib をコンパイルしたときの挙動を書いておく。
わたしのコンパイラもどきでは、以下のようになっている。
- fixnum は下位２ビットは 11 。
- LLVM なので SSA 形式、代入は一回限り。
- %ret は %eax レジスタのかわりに使っている。（正しい使い方かかなり怪しいが、とにかく何か値を返すときに必ず使っている）
- @main 関数が @scheme_entry 関数を呼ぶ。実際の処理は@scheme_entry に記述する、という構成。
- read は scheme 処理系 = gauche 任せ。
- i32 111 は #t, i32 47 は #f 相当。
まず、scheme （もどき）での fib。
gosh> (test-e "fib35" "9227465\n" '(labels ((fib (code (n) () (if (< n 2) n (+ (labelcall fib (- n 1)) (labelcall fib (- n 2))))))) (labelcall fib 35))) test fib35, expects "9227465\n" ==> ok 0.031699 0.580341 0.614444 #<undef>
これは、コンパイルされて以下のような .ll ファイルを生成。@Label_110 というのがフィボナッチ関数本体。
見るからに冗長なのは、SSA だから、という以外に、多分わたしが LLVM を良くわかっていないから、と思う。特にいちいち %ret に store/load している部分は根本的に間違ってる可能性あり。が、後述するようにどうせ最適化で単純化されるので気にしなくてもいい、と思いたい。
;; LLVM
define fastcc i32 @scheme_entry () {
entry:
%ret = alloca i32
store i32 140, i32* %ret
%var1676 = load i32* %ret
%var1675 = tail call fastcc i32 @Label_110(i32 %var1676)
ret i32 %var1675
%retval = load i32* %ret
ret i32 %retval
}
define fastcc i32 @Label_110 (i32 %arg1) {
entry:
; '@Label_110
; start-define
%ret = alloca i32
%sta247 = alloca i32
store i32 %arg1, i32* %sta247
%var1648 = load i32* %sta247
store i32 %var1648, i32* %ret
%sta248 = alloca i32
%var1646 = load i32* %ret
store i32 %var1646, i32* %sta248
store i32 8, i32* %ret
%sta249 = alloca i32
%var1647 = load i32* %ret
store i32 %var1647, i32* %sta249
%var1649 = load i32* %sta248
%var1650 = load i32* %sta249
%var1651 = icmp slt i32 %var1649, %var1650
%var1652 = select i1 %var1651, i32 111, i32 47
store i32 %var1652, i32* %ret
%var1644 = load i32* %ret
%var1645 = icmp eq i32 %var1644, 47
br i1 %var1645, label %Label_112, label %Label_111
Label_111:
%var1653 = load i32* %sta247
store i32 %var1653, i32* %ret
br label %Label_113
Label_112:
%var1660 = load i32* %sta247
store i32 %var1660, i32* %ret
%sta252 = alloca i32
%var1658 = load i32* %ret
store i32 %var1658, i32* %sta252
store i32 4, i32* %ret
%sta253 = alloca i32
%var1659 = load i32* %ret
store i32 %var1659, i32* %sta253
%var1661 = load i32* %sta252
%var1662 = load i32* %sta253
%var1663 = sub i32 %var1661, %var1662
store i32 %var1663, i32* %ret
%var1657 = load i32* %ret
%var1656 = call fastcc i32 @Label_110(i32 %var1657)
store i32 %var1656, i32* %ret
%sta250 = alloca i32
%var1654 = load i32* %ret
store i32 %var1654, i32* %sta250
%var1668 = load i32* %sta247
store i32 %var1668, i32* %ret
%sta254 = alloca i32
%var1666 = load i32* %ret
store i32 %var1666, i32* %sta254
store i32 8, i32* %ret
%sta255 = alloca i32
%var1667 = load i32* %ret
store i32 %var1667, i32* %sta255
%var1669 = load i32* %sta254
%var1670 = load i32* %sta255
%var1671 = sub i32 %var1669, %var1670
store i32 %var1671, i32* %ret
%var1665 = load i32* %ret
%var1664 = call fastcc i32 @Label_110(i32 %var1665)
store i32 %var1664, i32* %ret
%sta251 = alloca i32
%var1655 = load i32* %ret
store i32 %var1655, i32* %sta251
%var1672 = load i32* %sta250
%var1673 = load i32* %sta251
%var1674 = add i32 %var1672, %var1673
store i32 %var1674, i32* %ret
br label %Label_113
Label_113:
%retval = load i32* %ret
ret i32 %retval
}これを LLVM の機能(opt コマンド)で最適化すると、以下のようになる。ほとんど scheme で書いたのと変わらないくらいになっている。
- icmp slt i32 %arg1, 8 は %arg1 が 2 (タグによって４倍されて8)より小さいかを調べて
- その結果によって br でラベルにジャンプ。
define fastcc i32 @Label_110(i32 %arg1) nounwind readnone {
entry:
%var1651 = icmp slt i32 %arg1, 8
br i1 %var1651, label %Label_113, label %Label_112
Label_112:
%var1663 = add i32 %arg1, -4
%var1656 = call fastcc i32 @Label_110(i32 %var1663)
%var1671 = add i32 %arg1, -8
%var1664 = call fastcc i32 @Label_110(i32 %var1671)
%var1674 = add i32 %var1664, %var1656
ret i32 %var1674
Label_113:
ret i32 %arg1
}さらに、本来 @main は @scheme_entry 関数を呼び出すはずが、最適化で @main から直接 @Label_110 が呼ばれるようになっている。「手続き呼び出しの展開」という奴か。
疑問。勝手に付けられている tail オプションについて、未だに意味がよくわかっていない。これ tail じゃない気がするのだけど。。
;; main
define i32 @main() {
entry:
tail call fastcc void @scheme_initialize()
%var1656.i.i = tail call fastcc i32 @Label_110(i32 136) nounwind
%var1664.i.i = tail call fastcc i32 @Label_110(i32 132) nounwind
%var1674.i.i = add i32 %var1664.i.i, %var1656.i.i
%0 = tail call fastcc i32 @display_obj(i32 %var1674.i.i)
%1 = tail call fastcc i32 @newline()
tail call fastcc void @scheme_finalize()
ret i32 0
}
最適化
ここまでは以前と一緒。今度は末尾再帰版を書いてみる。
末尾再帰の最適化がちゃんと機能すれば、ジャンプ命令に変わりより速くなるはず。
追記；
うわー、そもそも末尾再帰になるように変更したら、関数の呼び出し回数が全然異なるから比較にならない。ぼけてる。別の例を探さなくちゃ。
以下を参考に。
http://d.hatena.ne.jp/SaitoAtsushi/20090208/1234085992
