OCaml で LLVM -- 事始め - camlspotter’s blog

この記事は LLVM-2.8 とその OCaml binding を使った LLVM プログラミングの始め方について、良く判らないという声を聞いたので、理屈はともかく、どうやって始めるかを主眼に書いた物です。OCaml や Makefile を全く書いた事が無いし知りたくも無い、でも LLVM を使いたいという方にはちょっと無理な内容になっています

clang とか LLVM とかこの頃よく聞きますよね。Apple が製品に結構使っているという話ですし、気になっている人もいるでしょう。私も LLVM、気になりました。要するに、プログラム内で Cみたいな言語(語弊がありますが)の構文ツリーを動的に生成して、それを、はいお願いと LLVM のエンジンに投げるとアーラ不思議、各アーキテクチャ用にいい感じで JIT コンパイルしてくれてスイスイ動く、という魔法のような話です。

マシン語は Z80 で止まっている、それも C9(=RET) 位しか覚えてないオジサンでもなんだかコンパイラの下の方が書ける、ような気にしてくれる、という訳。ライブラリ自体は C++ で書かれていて、ウヘェ、と思いましたが(実際はそんなひどいコードじゃないそうです)、なんと OCaml binding が付いてくる。飛びつかないわけにはいきません。なので早速使ってみましょう!

えーっと、 clang の事は気になりません。ごめんなさい。

Haskell でやりたいですって？コワい…

えっ、僕は Haskell が好きだから Haskell でやりますって？そりゃ大いに結構。

でも LLVM-2.8 + llvm-0.9.0.1 はビルドは出来るけど、全然使えませんよ。LLVM-2.8 では add と fadd を使い分ける必要があるんですが、それを全く考えずに、ただコンパイルできるようにしてあるだけ。テストを全くせずにリリースしてる。今俺が何故かパッチを書くはめになっちゃってるんだけど…まあ、誰も、作者さえも、使ってないってことね。

まあ、一番下のもろFFIっぽい.hscレイヤなら大変ですけど使えますから頑張ってください。まあ C のインターフェースそのまま持ってきてるから使えるの当たり前ですけどね…

LLVM-2.6 + LLVM-0.7.1.2 だとそれなりに動くみたい、です。

インストール

OCaml の LLVM binding は LLVM のソースにくっついてきます。だから、 OCaml をインストールした上で、 LLVM をビルド、インストールしてやれば、そのまま OCaml LLVM binding が使えるようになります。楽勝ですね。

え？ビルドが面倒だって？「故郷(くに)へ帰れ！ http://migzou.blog84.fc2.com/blog-entry-84.html 」

OCamlFind と一緒に使いましょう

よしインストールしたよ。せっかくだから、俺は OCaml で LLVM を使ってみるぜぇ！

いやちょっと待って下さい。多分そのままではリンクする時大変ですよ。Makefile にフラッグを一々書かなきゃいけないですから。

OCamlFind を使いましょう。 OCamlFind の META ファイルに必要なフラッグを llvm パッケージとして登録しておけば、後は -package llvm とすれば ocamlfind が勝手に必要なオプションを文脈に応じて使ってくれます。とっても楽。
https://bitbucket.org/camlspotter/ocaml-llvm-phantom/src/4f9dbe9a87ba/llvm-ocamlfind/ にあるファイルを三つ取ってきて(ocaml-llvm-phantom 自体を clone してもいいですけど)、./install-META.sh とすると勝手にごく適当に llvm の為の META ファイルを作って、あなたになんの了解も取らずに、次のようなファイルを llvm ocamlfind パッケージとしてインストールします:

requires = ""
version = "[llvm 2.8]"
description = "LLVM 2.8"
directory = "^"
browse_interfaces = " Llvm Llvm_analysis Llvm_bitreader Llvm_bitwriter Llvm_executionengine Llvm_scalar_opts Llvm_target "
archive(byte) = "llvm.cma llvm_analysis.cma llvm_executionengine.cma llvm_bitreader.cma llvm_bitwriter.cma llvm_scalar_opts.cma llvm_target.cma"
archive(native) = "llvm.cmxa llvm_analysis.cmxa llvm_executionengine.cmxa llvm_bitreader.cmxa llvm_bitwriter.cmxa llvm_scalar_opts.cmxa llvm_target.cmxa"
linkopts = "-cc g++ -cclib -L/home/jfuruse/.share/prefix/lib -cclib -lpthread -cclib -ldl -cclib -lm -cclib -lLLVMpic16passes -cclib -lLLVMMCDisassembler -cclib -lLLVMXCoreCodeGen -cclib -lLLVMXCoreAsmPrinter -cclib -lLLVMXCoreInfo -cclib -lLLVMSystemZCodeGen -cclib -lLLVMSystemZAsmPrinter -cclib -lLLVMSystemZInfo -cclib -lLLVMSparcCodeGen -cclib -lLLVMSparcAsmPrinter -cclib -lLLVMSparcInfo -cclib -lLLVMPowerPCCodeGen -cclib -lLLVMPowerPCAsmPrinter -cclib -lLLVMPowerPCInfo -cclib -lLLVMPIC16AsmPrinter -cclib -lLLVMPIC16CodeGen -cclib -lLLVMPIC16Info -cclib -lLLVMMipsAsmPrinter -cclib -lLLVMMipsCodeGen -cclib -lLLVMMipsInfo -cclib -lLLVMMSP430CodeGen -cclib -lLLVMMSP430AsmPrinter -cclib -lLLVMMSP430Info -cclib -lLLVMMBlazeAsmPrinter -cclib -lLLVMMBlazeCodeGen -cclib -lLLVMMBlazeInfo -cclib -lLLVMLinker -cclib -lLLVMipo -cclib -lLLVMInterpreter -cclib -lLLVMInstrumentation -cclib -lLLVMJIT -cclib -lLLVMExecutionEngine -cclib -lLLVMCppBackend -cclib -lLLVMCppBackendInfo -cclib -lLLVMCellSPUCodeGen -cclib -lLLVMCellSPUAsmPrinter -cclib -lLLVMCellSPUInfo -cclib -lLLVMCBackend -cclib -lLLVMCBackendInfo -cclib -lLLVMBlackfinCodeGen -cclib -lLLVMBlackfinAsmPrinter -cclib -lLLVMBlackfinInfo -cclib -lLLVMBitWriter -cclib -lLLVMX86Disassembler -cclib -lLLVMX86AsmParser -cclib -lLLVMX86CodeGen -cclib -lLLVMX86AsmPrinter -cclib -lLLVMX86Info -cclib -lLLVMAsmParser -cclib -lLLVMARMDisassembler -cclib -lLLVMARMAsmParser -cclib -lLLVMARMCodeGen -cclib -lLLVMARMAsmPrinter -cclib -lLLVMARMInfo -cclib -lLLVMArchive -cclib -lLLVMBitReader -cclib -lLLVMAlphaCodeGen -cclib -lLLVMSelectionDAG -cclib -lLLVMAlphaAsmPrinter -cclib -lLLVMAsmPrinter -cclib -lLLVMMCParser -cclib -lLLVMCodeGen -cclib -lLLVMScalarOpts -cclib -lLLVMInstCombine -cclib -lLLVMTransformUtils -cclib -lLLVMipa -cclib -lLLVMAnalysis -cclib -lLLVMTarget -cclib -lLLVMMC -cclib -lLLVMCore -cclib -lLLVMAlphaInfo -cclib -lLLVMSupport -cclib -lLLVMSystem "

うわあ長いね！でも逆に言うと、このファイルを作っとかないと一々 Makefile にこれを打ち込まなきゃいけない訳でして… 悪いことは言わないから作っておきましょう!

Makefile/OMakefile から

じゃあ、 Makefile から始めましょう。 test.ml ってファイルを書いて、 test っていう実行ファイルを作ることにします:

# TAB が潰れているので自分で直してね!!
test: test.cmx
    ocamlfind ocamlopt -package llvm -o $@ $<

%.cmo: %.ml
    ocamlfind ocamlc -package llvm -c $<

%.cmx: %.ml
    ocamlfind ocamlopt -package llvm -c $<

.PHONY: clean

clean:
    rm -f *.cm* *.o test

超ミニマルにはこんな感じでしょうか。 ocamlfind で各OCamlコマンドをラップして、 -package llvm を付ける。そいだけ。そうすると上の META ファイルに書いてあるオプションを適宜付け加えてコンパイラを起動してくれる。ソースも一ファイルしかないから簡単ですね。

OMake http://omake.metaprl.org/ が好きという方の為にも OMakefile ならどう書くかも書いときましょう:

# OMakeroot は自分で作ってくれい
USE_OCAMLFIND=true

OCAMLPACKS[]=
    llvm

FILES[] =
    test

.DEFAULT: test

OCamlProgram(test, $(FILES))

.PHONY: clean

clean:
    rm -f $(filter-proper-targets $(ls R, .))

ソースが一ファイルしかないと Makefile も OMakefile も長さはあまり変わりませんが、ややこしくなってくると OMake の方が吉です。まあ、 Makefile で遊んでいるうちに収集つかなくなったら OMake に移行してみるのを検討してみてください。

初めての LLVM を使ったコードを書こう

さて、ようやく肝心のソースコード、 test.ml を書きましょう!

目標は、与えられた 32bit の整数を二倍にして返す関数 double を LLVM で定義、コンパイルして、実行する。

です。簡単すぎますか？いやいや、まあ、まずは簡単すぎるものから始めたほうがいいですよ。

まずは準備: エンジン、コンテクスト、モジュール、ビルダ

open Llvm

module E = Llvm_executionengine

let _ = E.initialize_native_target ()

let context = global_context ()

let module_ = create_module context "mymodule"

let builder = builder context

まずは準備です。この辺はまあ、呪文のようなものです。

Llvm_executionengine とか、とにかくモジュール名が長いので、 E とか、短縮名をつけましょう
E.initialize_native_target () しないと JIT コンパイルしてくれず、ただのインタプリタになります。インタプリタでも動くけど遅いよ!
context というなんかよくわかんないものが至るところで必要です。普通は global_context () しか使いません。
関数はモジュールに定義します。 "mymodule" という名前のモジュールを作りましょう。
ビルダ builder も作っておきます。これは現在作業している場所を示すカーソルやポインタみたいなものです。
build_hogehoge 引数 builder という関数がよく出てきますが、これは現在 builder が差している所に
hogehoge というインストラクションを付け加えてねって意味です。

さて、ここまでのコードを test.ml に書いて、 make なり omake でビルド、実行できましたか？まあ、実行といっても画面には何も出力されませんが...これがまず第一歩です。

えぇ？ビルドできない？ちゃんと上の準備やりましたか？ ocamlfind の META とかやってない？そんな人の事は知りません。

型を定義

さて、よく使う型をここで定義しておきましょうか。 test.ml の続きです(これからも test.ml に足していきます):

let i32_t = i32_type context

上のコードは context 中で 32bit の整数型を i32_t として定義します。こんな風に OCaml LLVM binding では何か基本型を作るときにすぐ context を要求するのですが、面倒ですね。なので、前もってこうやって定義しておくのがよいでしょう。

さて double 関数を定義!

関数を定義するには、まず関数の型を作って、こういう関数があるよと宣言しなければいけません。C の関数プロトタイプ宣言のようなものです:

let double_type = function_type i32_t [| i32_t |]

let double = declare_function "double" double_type module_

double_type で i32_t を一つ受け取り i32_t を返す関数の型を定義して、module_ では "double" という名前の関数がその型を持ちますよー、と宣言しています。

さて、肝心の関数の定義に移りたいと思ますが、その前に:

let bb = append_block context "entry" double

let () = position_at_end bb builder

LLVM ではコードは関数内のベーシックブロックに書かなくてはいけません。ベーシックブロック内のコードは順に実行されます。条件分岐やループはベーシックブロックを複数作り、それらをブランチ命令で繋げる事で実現しますが、今回はパスします。ここでは "entry" という名前のベーシックブロックを double 関数に付け加え、ビルダをそのブロックの最後（といってもまだコードが何も無いので先頭です）に移動します。

double 関数は引数を二倍して返す関数ですから、引数を使えないと何にもなりません。まずは引数を取り出しましょう:

let param = match params double with
  | [| param |] -> param
  | _ -> assert false

params 関数で double の引数配列を取得できます。一引数しかないはずです。さて、ここで param は引数を指し示す llvalue という型を持つ値ですが、llvalue は何か具体的な値を意味するのではない事に注意してください。Value というからには何か値が取り出せそうな気がしますが、そうではありません。大雑把に言うと、何かしらの計算結果が入った変数を指し示すものだと思えばよいでしょう。例えば、この場合は関数が実行時に渡された引数になりますね。

llvalue には名前を付けることができます。せっかくなので引数に "param" という名前を付けてみます:

let () = set_value_name "param" param

さて、この param を二倍するコードを生成しましょう:

let doubled = build_mul param (const_int i32_t 2) "doubled" builder

build_mul x y name builder は x と y という llvalue の内容を掛けて、 name という名前の llvalue に結果を格納するコードを builder が指し示している場所に加えます。ここで const_int i32_t 2 は 32bit 整数の 2 を生成しています。結果の llvalue は doubled という変数に束縛されます。この結果を build_ret を使って関数の返り値にすれば出来上がりです:

let () = ignore (build_ret doubled builder)

ダンプしたり、整合性をチェック

なんだか良くわかった様な、わからん様な．．．そこでこの定義された関数をダンプしてみましょう:

let () = dump_value double

そうするとこんなのが表示されるはずです:

// おっとコレは OCaml のソースじゃないよん
define i32 @double(i32 %param) {
entry:
  %doubled = mul i32 %param, 2
  ret i32 %doubled
}

どうでしょう。 Cっぽい文法で、今まで構築してきた型やコードが double 関数の定義に組合さっているのがわかるでしょうか。i32 という型の %param を受け取って、%param と 2 を掛けて、その結果 i32 の %doubled を返す、そんな風に読めるはずです。

しかし本当にこのコードで正しいのでしょうか。そんな心配症のあなたのために、LLVM ではコードに致命的な間違いがないかチェックする Llvm_analysis.assert_valid_function 関数があります:

let () = Llvm_analysis.assert_valid_function double

もし double 関数の内部の型が間違っていたり、妙なことをしていると、ここでエラーを吐きます。このエラーメッセージは慣れないと良く意味が判らないのですが、それでも assert_valid_function は是非呼出すべきです。ここで聞かないと後でもっと意味のわからないエラーに悩まされることになりますから。もちろん、このエラーチェックで検査できるのは型の整合性だとか、SSA形式になっているだとか (SSAを知らない人は取りあえずほっといていいです)、そういうことだけで、全ての問題を検出できるわけではありませんが、それでも有益です。(Haskell の LLVM はこのチェックをサボっているので、バグが直しにくいこと...噴飯物です)

いざ実行!

さて、ようやく実行です。 dump で見たコードを実際に LLVM のエンジンに渡し、コンパイルした上で、引数を与えて実行してみましょう:

let engine = E.ExecutionEngine.create module_

let res = E.ExecutionEngine.run_function double [| E.GenericValue.of_int i32_t 21 |] engine

let res_int = E.GenericValue.as_int res

let () = Printf.eprintf "double(21)=%d\n" res_int

まずは ExecutionEngine.create で実行エンジン engine を作り、ExecutionEngine.run_function で double 関数を engine 上で JIT コンパイルし、さらに引数を与えて走らせます。この際の引数は E.GenericValue.t という型を持っていて、 llvalue と違って本当の値です。ここでは E.GenericValue.of_int i32_t 21 で 32bit 整数型の値 21 を作っています。結果 res も E.GenericValue.t ですから、実際に値を取り出せます。これを OCaml の整数に as_int で変換してプリントアウトして終了。ちゃんと上手くいっていれば結果が 42 になっているはず...です。

LLVM を使ったプログラミングってこんな感じ

どうでしょう。凄く簡単な LLVM の関数を OCaml binding を使って定義し、実際に JIT を使ってコンパイルし、走らせてみました。手順はこんな感じ:

関数の型（プロトタイプ）宣言をする
ベーシックブロックを関数にくっつける
ビルダをコードを足したいべーシックブロックに移動
コードを build_hogehoge 命令で付け加えていく
複数のベーシックブロックが有るばあいはそれをブランチ命令で繋ぎあわせる(今回はパス)
build_ret で返値をリターン
assert_valid_function で定義をチェック
エンジン上で JIT コンパイル＋実行

単純な二倍する関数にこんな手間かけてどうすんだという気もします。確かにその通りで、 double を定義するだけなら上でダンプしたコードをそのまま書いてLLVM のアセンブラ（だっけ？）に渡せばそれで終わり。

一方、 LLVM の C++ API や OCaml binding は凄く手間がかかります、でもその分、動的にホスト言語(C++ や OCaml)から LLVM のコード木を生成し、そのコードを JIT コンパイル+実行させ、その結果をホスト言語でまた使う、といった面白い事が出来るようになるのです。これは結構楽しいですよ。

例えば自分のプログラミング言語処理系を OCaml で書いて、ネイティブコードにコンパイル、実行する部分を LLVM でやる、とか。パースや型検査は言語処理に向いた関数型言語でやって、実行はインタプリタだと今時ダセェし遅いからマシン語に変換するわけです。簡単にオレオレ言語の REPL が作れちゃいますよ！皆さんも試してみてね！

LLVM、ここからどうするか

さて、

オレはようやくのぼりはじめたばかりだからな
このはてしなく遠い LLVM 坂をよ...
未完

− 菊川仁義

そうですね、例えば LLVM のページにある Kaleidoscope というオモチャ言語の OCaml 版 http://llvm.org/docs/tutorial/OCamlLangImpl1.html を試してみたらどうでしょう。CamlP4 を使ったパーサ部分の実装から入っているので、言語処理系内部をいじったことの無い人には良いかもしれません。逆に、その辺知ってる人はパーサ部分はすっ飛ばして自分の好きな lex+yacc なり parsec なりで書けばよろしい。

ただ、このチュートリアル、ちょっと古いのです。例えば double の足し算を add 命令でやっているのですが、これは fadd を使わないと LLVM 2.8 ではエラーになっちゃう。その辺り、つまづきポイントがありますね...まあ、一言でいうと、

LLVM坂は基本地雷原

という事ですわ。ドキュメントがちょっと古い、とか、前のバージョンだと動いていたのに、現バージョンだと挙動がおかしいとか、結構あります。それでメゲルようなら、

最初から LLVM プログラミングなど手を出さないほうが良い

のです。さよぉおならぁああ。

Phi とか SSA とか。

今回の単純な例では条件分岐が全くなかった訳ですが、条件分岐があるコードを LLVM で書きたい場合には、SSA形式とか、Phi関数とか、宇宙、それは人類最後のフロンティア、とかお勉強したほうが良いかもしれませんですわね、あてくし自身なにも覚えておりませんが。おほほほ。(思い出しました。ドミナンスフロンチアでした。http://en.wikipedia.org/wiki/Dominator_(graph_theory) )

OCaml binding メンドイ

OCaml binding で LLVM 書いてると、数時間後に、

なんで一々 context って書かなあかんねん
なんで一々 builder って書かなあかんねん
なんで何でもかんでも llvalue やねん、これじゃあ
assert_valid_function で定義チェックするまで型エラーわからんやないか
なんで変な gep 作ったら segfault で落ちんねん
なんで以下略

とか、いろいろ問題点が見えてきます。困りますよねぇ。
そこんとこ何とかしようといろいろ頑張っているところです。お楽しみに。

疲れた

めずらしく優しい口調で書いてみたら疲れたよ…

test.ml の全体だよお

open Llvm

module E = Llvm_executionengine
  (* Llvm_executionengine って一々書いてられないから E って名前をつけます *)

let _ = E.initialize_native_target ()
  (* これをしないと JIT が有効にならず、ただのインタープリタになっちゃって遅くなるよ *)

let context = global_context ()
  (* このコンテクストってのをいろんなものが要求します。面倒だね *)

let module_ = create_module context "mymodule"
  (* モジュールを作りましょう *)

let builder = builder context
  (* ビルダを作りましょう。 build_hogehoge 引数 builder すると、
     hogehoge という命令を builder が指している所に作ってくれる。
     カーソルみたいなものです。 *)

let i32_t = i32_type context
  (* 32bit 整数の型。何度も i32_type context って書くの面倒だから定義しとこう *)

(* 準備終わり！ double 関数を定義していきましょう!! *)

let double_type = function_type i32_t [| i32_t |]
  (* double 関数の型。 i32_t を一つ受け取って i32_t を返す *)

let double = declare_function "double" double_type module_
  (* "double" という関数が double_type を持つと宣言します。 *)

let bb = append_block context "entry" double
  (* double 関数に "entry" という名前の basic block を付け加えます。 *)

let () = position_at_end bb builder
  (* ビルダを bb を指すようにして、 build_hogehoge が double 関数のコードを生成するようにします *)

let param = match params double with
  | [| param |] -> param
  | _ -> assert false
      (* double 関数の引数を指す llvalue を得ます。一引数だから、一つしか帰ってこないはず *)

let () = set_value_name "param" param
  (* 引数に名前はつけなくてもいいけど、せっかくだから俺は "param" って名前をえらぶぜぇ *)

let doubled = build_mul param (const_int i32_t 2) "doubled" builder
  (* param を 2 倍するコードを生成します。結果を利用するには doubled を使う *)

let () = ignore (build_ret doubled builder)
  (* doubled を関数の戻り値にするよ *)

(* double 関数は定義できた!! *)

let () = dump_value double
  (* 念のため、 double をダンプしてみる。コードがプリントアウトされるよ。それとなく二倍してるっぽいでしょ？ *)

let () = Llvm_analysis.assert_valid_function double
  (* 折角だから、 LLVM 様に俺のコードが正しいか聞いてみるぜぇ！
     というか、お願いですから必ず聞いてください。ここで聞かないと後で後悔します。
     もしここでエラーが出るといろいろ言われます。はじめは意味がわかりませんが、めげてはいけません。
     チェックをせずに後で文句を言われた場合、もっとわけがわからなくなります。 *)

(* double 関数はチェックできたよ！ さあ、 LLVM 様にコンパイルしてもらおう! *)

let engine = E.ExecutionEngine.create module_
  (* LLVM engine を作るよ! *)

let res = E.ExecutionEngine.run_function double [| E.GenericValue.of_int i32_t 21 |] engine
  (* Engine に double 関数をコンパイルして、その上 21 を適用して結果をもらいます *)

let res_int = E.GenericValue.as_int res
  (* 結果を OCaml の整数に変換するよ *)

let () = Printf.eprintf "double(21)=%d\n" res_int
  (* ちゃんと 42 になっていますかぁ？ *)

Haskell でやりたいですって？ コワい…