beflisp.bef と LLVM Befunge backend
https://github.com/shinh/beflisp
Lisp インタプリタを作りました。今度は Befunge で。
https://github.com/shinh/beflisp/blob/master/beflisp.bef
コードを見ればわかりますが、手書きは諦めました。 前回の sed と違って Befunge は数値演算は素直に提供してくれてるので、アドレス計算なんかをするプリミティブが提供しやすいです。ただ、 Befunge-93 は文字列とか関数コールという概念が無いので、手動でフロー管理するのは地獄でしょうね…
ということで、 C で lisp を書いて、それを clang で LLVM bitcode に変換してから、トランスレータで Befunge に変換、という構成になっています。
実装
トランスレータは任意の C コードを Befunge に変換できるようなレベルには全然達していません。例えば型は全部 32bit 決め打ちです。内部実装知ってないとどういう C コードなら通るかとかわかりにくいでしょうし、内部実装知ってる私にもあまりわかってません。ていうかなんで動いてるんだろうっていう感じ。全体的に投げ槍な実装なんで。
LLVM bitcode からトランスレートされた Befunge コードってのは、あたりまえですが割とデバッグが大変です。しょうがないので小さな C プログラムを一つずつ動くようにしていく感じでやりました。あとデバッグしやすいように元に bitcode を実行しない領域に置いてあります。
大変だったのはまずブランチとかですかね。立体的にコード配置するのはデタラメに大変に決まってるので直線的に実行したいので。スタックトップが真ならスタックの2番目を採用、偽なら3番目を採用、ってことができるプリミティブを作ってそれをあちこちで使う感じにしました。ブランチといえば当然 PHI もダルいったらありゃしない。
LLVM のバックエンドの書く作法を調べるのが面倒だし、 LLVM のバックエンド用の共通基盤が Befunge みたいな素頓狂な実行モデルにうまいこと適合するとは思いがたかったので、 bitcode 読んでからは全自力です。レジスタアロケーションだけやってもらえたりするとラクに生成されたコードを小さくできるんですが…
機能としては前回の sed と同じはずです。前回のテストコードは全部パスしてますし、 FizzBuzz on Lisp on Lisp on Befunge も動いています。すごく遅くて、半分で 1 時間とかかかってますけど。
TODO
レジスタアロケーションをやるってのと、ブランチの高速化、ってのがあります。このふたつやればもう少し実用的な速度になるんでないかなぁと。
というのは、前者は、現状 SSA の結果は全部スタックに残していっていて、スタックがまあまあ遠いところにあるんでアクセスにかかる命令数が多いということがあり。
後者はもっとひどい話で、現状どこかで jmp や call があると、必ずプログラムの一番先頭まで戻ってから次に実行する場所を線型探索してます。そうでなくてちゃんと差分だけ動くようにすれば、近くへの jmp とかが劇的に速くなるかと思います。
あとは free が実装されてないってのがひどいんですけど、当然のことながら実装するとすごく遅くなっちゃうと思われるので、だるいかなあと。
まとめ
Befunge はまともな言語
