Scheme Compiler の勉強(40) - proper tail call

scheme

Tail call を以下のように実装中。あちこち理解が怪しいので注意。このテストが通れば tail call optimization は大丈夫、という例が欲しい。

  • まず現状の整理。手続き呼び出しは、今のところどんくさいが closure に対する funcall と llvm の関数を直接呼ぶ labelcall とがある。(そのうちに奇麗にする。)
  • lambda で定義される関数を LLVM の関数にコンパイルする際、全て fastcc オプション(fast calling convention)を付与するようにした。デフォルトの ccc オプション(C calling convention)を使っていないことで問題になるかもしれないが問題になったときに考える。
  • labelcall の tail call 版の tail-labelcall を定義。これは最終的に tail オプション付きの LLVM call インストラクションにコンパイルされる。(labelcall と tail-labelcall とはほとんど同じで冗長なので、うまく統合する方法を考えたいがとりあえず。）
  • コンパイラ側で、tail-call-conversion なる手続きを作る。これは与えられた式の末尾コンテキストを探し、さらに末尾コンテキストで labelcall をしている場合に限りそれを tail-labelcall に変換する。

これで以下のような再帰呼び出しが tail call に変換されてちゃんと動作するようになった。

gosh> (run-program '(labels ((e (code (x) () (if (zero? x) #t 
                                           (labelcall o (sub1 x)))))
                       (o (code (x) () (if (zero? x) #f
                                           (labelcall e (sub1 x))))))
                (labelcall e 1000003)))
"#f\n"
gosh> (run-program '(labels ((e (code (x) () (if (zero? x) #t 
                                           (labelcall o (sub1 x)))))
                       (o (code (x) () (if (zero? x) #f
                                           (labelcall e (sub1 x))))))
                (labelcall e 1000002)))
"#t\n"

最適化前は以下のとおり。tail call をちゃんと指定しているので、 -tailcallopt のみでちゃんと実行できている様子。手抜きというか自分のコンパイラの構成がダサイため、tail call - ret の後にさらに絶対に到達しないコード片がある。LLVM で最適化すればどうせなくなるのでしばらく放置（！）。

define fastcc i32 @Label_154 (i32 %arg1)  {
entry:
    ; start-define
    %ret = alloca i32
    %sta42 = alloca i32
    store i32 %arg1, i32* %sta42
    %var579 = load i32* %sta42
    store i32 %var579, i32* %ret
    %var580 = load i32* %ret
    %var581 = icmp eq i32 %var580, 0
    %var582 = select i1 %var581, i32 111, i32 47
    store i32 %var582, i32* %ret
    %var577 = load i32* %ret
    %var578 = icmp eq i32 %var577, 47
    br i1 %var578, label %Label_159, label %Label_158
    Label_158:
    store i32 47, i32* %ret
    br label %Label_160
    Label_159:
    %var586 = load i32* %sta42
    store i32 %var586, i32* %ret
    %var587 = load i32* %ret
    %var588 = sub i32 %var587, 4
    store i32 %var588, i32* %ret
    %var585 = load i32* %ret
    %var584 = tail call fastcc i32 @Label_153(i32 %var585)
    ret i32 %var584
    br label %Label_160
    Label_160:
    %retval = load i32* %ret
    ret i32 %retval
}

なお最適化すると phi 関数とか出てきてもはやちゃんと関数呼び出しさえしていないような・・。理解するにはまだまだ LLVM を勉強しなくては。