Scheme Compiler の勉強(30) - tail call

scheme

http://d.hatena.ne.jp/cranebird/20081106 の続き。

自作トイコンパイラで tail call 対応したので以下のテストが通るようになった。

gosh> (run-program '(letrec ([e (lambda (x) (if ($fxzero? x) #t
						(o ($fxsub1 x))))]
			     [o (lambda (x) (if ($fxzero? x) #f
						(e ($fxsub1 x))))])
		      (e 5000000)))
address: <00000000000000000000000001101111>
optimize..."#t\n"
gosh>

素晴らしい！と自画自賛したいところだけど、 llvm レベルでの最適化を行っただけで、トイコンパイラは依然としてトイコンパイラのまま。

  • S-式 => [自作の"コンパイラ" run-program] => LLVM IR(S-式) => LLVM IR(テキスト) => [llvm-as] => LLVM IR (バイナリ) => [opt] => LLVM IR (最適化されたバイナリ) => [llc] => マシン固有アセンブラ(ここではPowerPC) => [llvm-gcc] => 実行ファイル、となる。
  • opt は最適化を行う。コマンドは http://www.llvm.org/docs/CommandGuide/index.html 参照。
  • 最適化をしたら動く可能性は気付いていたのだけど、普段オフにしていたフラグをオンにしたつもりがなってなかった‥注意力不足と分かりやすい表示を自分に提供するのをさぼっていた罰。
  • 最適化の結果は、（面倒だけど）一旦 LLVM IR のバイナリからテキストへ llvm-dis(ディスアセンブラ)で戻して眺める。
  • tail call どころか定数になってる？？よし、ちゃんと少しずつ最適化のレベル(= opt に与えるオプション)を変えながら、最適化結果をちゃんと眺めよう。
  • 素朴な疑問。LLVM の最適化が高度すぎて、scheme 言語レベルでの最適化をまったくやっていなくて不味い。「継続」が出てきた時に細部を詰めていないツケとして、恐らく全体を書き直すことになるだろう。が、それもまたよし。


続く。

opt のオプション

  • 多すぎる。最適化のオプションのみで約100。-std-compile-opts だけで78。
  • まず LLVM のレベルで tail call だけになるようにしたい。そして本当に tail call になっているか確認しよう。手で実行するのは面倒なので scheme で。
    • まず「-std-compile-opts を指定して最適化すると成功するけどしないと失敗する」コードであることを確認。
    • １個ずつ最適化オプションを与えただけだと全部失敗。ということは組み合わせる必要がある。
    • tailcallelim だけ除くと失敗、ただし tailcallelim だけでも失敗。
    • うん？-std-compile-opts を指定した場合と、それに含まれるもの全部を指定したつもりの結果が違うような。

http://www.llvm.org/cmds/opt.html に書いてある方法

llvm-as < /dev/null | opt -std-compile-opts -disable-output -debug-pass=Arguments

で std-compile-opts を取得したのだが、この結果は -lcssa が何回も出てきてる？
あ、やっと分かった。llvm の中間コードに対する最適化は、行う最適化の順番を自由に(in any order)指定できるのか。ちゃんとマニュアルに書いてあった。

  • {passname}

opt provides the ability to run any of LLVM's optimization or analysis passes in any order. The -help option lists all the passes available. The order in which the options occur on the command line are the order in which they are executed (within pass constraints).

http://www.llvm.org/cmds/opt.html

続く。