2012年12月17日

SML#をLLVMに変換する

この記事はLL/ML アドベントカレンダーの記事です。なごやに向かって不用意な発言をすると勝手に登録されるので皆さん気をつけましょう。

SML#の0.90リリース以来、私はSML#の美しさに魅せられ……ることは別になく、もっぱらその低レベルプログラミングとの相性からSML#の使い方を妄想するなどの健全な遊びをしておりました。
SML#はなかなか楽しい言語です。特に怪しいC/C++のライブラリをwrapするのには、SML#は極めて強力な道具となることが期待されます。
こうした処理を、ストレスなく書ける処理系として、私はSML#に密かに期待しておりました。

が。

SML#を使うにあたって、そこには大きな問題があります。

x86では動くけど、ARMで動かない! POWERで動かない! SPARC64VIIIfxとかで動かない! せめて、x86_64で(32-bit libsなしで)動いて欲しい! 今時x87命令とかありえない!

あすてりずむさんも書かれていますが、やっぱりARM用コンパイラほしいですよね!
http://d.hatena.ne.jp/aster_ism/20121207/1354806769

SML#コンパイラを読み解くとわかりますが、SML#のアセンブラコード出力は血のにじむような努力の末に達成されています。
これを書き換え、ARMやx86_64向けに出力するには、おそらく1出力先ごとに1ウエノ(単位)相当の生贄を捧げねばならないと言われております(ません)。
これは大変な作業なので、おいそれと要求できるものではありません。また東北大のコアデベロッパーの方々には、レジスタ割付や命令列の並び替え、変換などよりも、むしろ彼らにしかできない言語側の仕事を頑張って欲しいものです。

……ということで、無いものは自分で作れという声を聞きまして、SML#からさまざまな他アーキテクチャに向けてコードを出力しようと思い立ちました。今考えるとC言語で出力しても別によかったかなと思うのですが、ジャンプや例外の処理を考えると、C言語よりもう少し柔軟な出力先を選びたくなります。今回やってみたのが、LLVM (Low Level Virtual Machine)での出力です。LLVMはコンパイラを作るための共通基盤として作られた抽象VMで、LLVMのアセンブラとして記述されたコードは様々なアーキテクチャのコードに変換が可能です。LLVMはLLVMをC言語として出力する機能もあるので、いざとなればC言語での出力も可能です。万一SX-9でプログラムを走らせることになっても、大丈夫。そう、LLVMならね。

コードはこのへんです。READMEに書きましたが、言語の最小セットの部分しか実装していません。具体的には、追加された例のminimal.smlしかコンパイルできません。

https://github.com/shunsakuraba/smlsharp/tree/llvm

実装ですが、SML#コンパイラでは、AbstractInstruction2という抽象マシンコードから、ターゲットアーキテクチャの言語に変換を行います。このAbstractInstruction2はかなり抽象度が高いコードになっており、無限レジスタ上での逐次命令列が記載されています。この命令はほぼ1対1でLLVMの命令に対応します。ですから、ほとんどただ逐語訳するだけで変換はOKです。

ね、簡単でしょ?

「ほとんど」ではなかった点は以下の通りになります。
・LLVMに於いて、グローバル定数はデータではなくデータへのポインタとして扱われる。AbstructInstruction2では、グローバル定数はデータとして扱われる。このため扱いが面倒である。
・LLVMでは関数を異なる引数型で再定義することはできないので、何かの関数を異なる型で呼びたい場合はcastにより実装する。具体的にはprintfの書式違いとかな!
・AbstructInstruction2ではポインタにあたるものは何でもBOXED型だが、LLVMでは「それが何のポインタか」まで問われるため、変換しようとすると多くの場合情報が不足する。たとえばC-stringのようなものは、SML#ではBOXEDだが、LLVMではi8*型である。内部の処理の都合上、i32*型などにキャストして置かなければならない。
・上記と合わせ、基本的にAI2では型情報がいくつか抜け落ちている。真面目にやるなら間に1枚新たな構文木を挟んで、型を復活させてから変換したほうが筋が良さそうである。

あとは、単に作業です。未実装部分をraise NotImplementedで埋めておいて、引っかかるたびに延々とパターンマッチを書く簡単なお仕事! 今後はGCや例外を実装したいところです。

追記:llvm 2.9では動いていたのですが3.0では動かない模様なので今度fixします。
posted by chun at 00:02| 関数型