As Sloth As Possible

可能な限りナマケモノでありたい

タグ:LLVM

ゴールデンウィークを利用して久々にろくでもないものができたので晒しておく。

「ごっこじゃないよ、兄ちゃん!」「才能の無駄遣いじゃなくて、無駄そのものだよ、お兄ちゃん。」

前のと何が違うの?

そもそもの発端についてはプログラミング言語「DT」という記事を、実際の言語仕様についてはREADMEでも読んでもらうとして、何で再実装したのかという話。

3年前に作ったのは「Whitespaceのトークンを置換した処理系をインタプリタとしてRubyで実装」したものなんだけど、何を思ったかコンパイルしてみたいと思い立ってしまい、んでそれ自体はLLVMが良く分かんなかったとか、llvmruby自体がプロジェクトとして大分アレな感じになってしまっていたとか、そういう事情で挫折してたんだけど、時は流れ、なんか見返してみたら普通にLLVMアセンブリ読み書きできるようになってたし、ruby-llvmがちゃんと動くようになってるみたいだし、ということで再実装してみることにした。

そんで作り直す過程で「Whitespaceの置換ってのもなんだか面白くないな」と思ってVMのアーキテクチャと言語仕様を見直すことにした(ぱっと見だと全然分かんないけど、旧DTと新DTの間に互換性は無い)。そのせいで実際にはチューリング完全じゃなくなってると思うし、そもそもちゃんと出来てるのかどうか怪しいものだけど、とりあえず「Hi!」って出力するのとフィボナッチ数を出すのは動いたので良しとする。

当初の目標だった「DTコードをネイティブのバイナリにまでコンパイルして高速に実行」ってのも実現して、DTインタプリタで250msくらいかかるfib.dtをコンパイルすると4msくらいで結果が出るようになった。似たようなRubyのコードだと大体100msくらいだったので素敵に速い。まぁ、コンパイル自体はLLVMとコンパイラに任せているので大して威張れるあれでもないのだけども。そして高速に動いたからなんだという話なのだけども。

ぶっちゃけDTよりLLVMアセンブリの方が遥かに記述力高いし書きやすい。当たり前のように構造体とか関数ポインタとか使えるのな。Cの関数呼べるし。最初Cで書いてたVMを途中でLLVMアセンブリ直接書くようにしたけど、大して変わらない。DTで書くくらいならLLVMアセンブリ書いた方がいいです。LLVMの無駄遣いタグを付けていただきたい。

DTの存在意義については疑問を差し挟む余地もなく皆無だと言っていいけど、その過程でレジスタマシンについて色々調べて、はー、こんぴゅーたーってこうやってうごいてるのかー、と勉強になったのでそれはそれで良かった。よくこんなの考えられるよなぁ。CPUとかコンパイラとか作ってる人達、本当に俺と同じ種類の生き物なのだろうか。凄い。

懲りずにesotericでDTのコンパイラを作るべくしこしことコードを書き続けているのだけど、コンパイラ(というかesotericのASTからLLVMへのブリッジ)は概ね出来たので、今は各言語のパーサを直しつつ標準ライブラリをLLVMアセンブラで書いてる。別に標準ライブラリはCで書いてllvm-gccとかでコンパイルしておけばいいっちゃいいんだけど、なんとなく、出来るだけLLVMとllvmruby以外には依存しない方針で行こうと思ったため。Cで書いたのをコンパイルするととしれっとターゲット指定されてたり外部のライブラリの関数呼んだりしてるので、ちゃんと使い方わかんないとどうなるか良く分からなかったので。

LLVMアセンブラむずい

…で、すぐにそれを後悔することになったわけですが。これがまぁ、今までRubyとかPerlとかばっかり書いてた身にはLLVMアセンブラはなかなか難しい。いやもちろんいわゆる「アセンブラ」よりはずっと書き易いし、それどころかDTのコード書くよりも遥かに楽(なんだろうこの本末転倒っぷりは)なんだけども、そうは言っても、ねぇ。Cだって読めはするけどあんまりまともに書いたことないし、それでアセンブラっつってもね。で、まず、以下のような関数を書こうとしてハマる。

void stack_copy(int n) {
    ESONODE *node = stack_top;
    while (n > 0) {
        node = node->next;
        n--;
    }   
    stack_push(node->value);
}

スタックの上からn番目の値をコピーして、スタックの一番上に詰む処理ですね。ちなみにESONODEは値と次の要素へのポインタを持つスタック要素の構造体、stack_topはスタックの一番上に乗ってるESONODE、stack_pushは見て分かるようにintの値を取ってそれをスタックの一番上に乗せる関数。さてここで「whileってどう書くんだろう…」と10分くらい途方に暮れる。LLVMアセンブラにはループ構文は無い。ぼーっとしてても分かるわけもないので、llvm-gccで一旦上記のソースをコンパイルしてからllvm-disでバイトコードをLLVMアセンブラに戻して見てみることにする。で、それを参考に書いたのが次のコード。

define void @dt.stack_copy(i32 %n) {
entry:
    %n_ptr      = alloca i32
    %node_ptr   = alloca %struct.ESONODE*
    store i32 %n, i32* %n_ptr
    %top        = load %struct.ESONODE** @dt.stack_top, align 4
    store %struct.ESONODE* %top, %struct.ESONODE** %node_ptr, align 4
    br label %loop_cond
loop_body:
    %node       = load %struct.ESONODE** %node_ptr, align 4
    %next_ptr   = getelementptr %struct.ESONODE* %node, i32 0, i32 1
    %next       = load %struct.ESONODE** %next_ptr, align 4
    store %struct.ESONODE* %next, %struct.ESONODE** %node_ptr, align 4
    %n1         = load i32* %n_ptr, align 4
    %res        = sub i32 %n1, 1
    store i32 %res, i32* %n_ptr, align 4
    br label %loop_cond
loop_cond:
    %n2         = load i32* %n_ptr, align 4
    %cond       = icmp sgt i32 %n2, 0
    br i1 %cond, label %loop_body, label %return
return:
    %_node      = load %struct.ESONODE** %node_ptr, align 4
    %val_ptr    = getelementptr %struct.ESONODE* %_node, i32 0, i32 0
    %val        = load i32* %val_ptr, align 4
    call void @dt.stack_push(i32 %val)
    ret void
}

…むぅ。まずはスタックトップを取ってきて%node_ptrがそれへのポインタになるようにする。あと、引数%nのポインタも作ってる。なんでこんなことしてるのかなーと思ったけど、ローカルの変数それ自体は一度定義したら不変なのね。なのでポインタとstoreとloadを使って、「変数に再代入」しているのではなくて「ポインタが差し示す先を変え」ているってことなのかな。多分。これでCのコードでnodeやiを操作してるのと同等のことをしてる。

最初の準備を終えたら次にラベルloop_condにジャンプしてる。そこでポインタ%n_ptrが差し示す先の値が0より大きいかを見て、0より大きければloop_bodyへ、0以下だったらreturnにジャンプ。loop_bodyでは%node_ptrの差し示す値が次のノードになるように変えるのと、%n_ptrが差し示す値がその時点での値から1引いたものになるように変える。んでまたloop_condへ。%n_ptrの値が0になるまではloop_condとloop_bobyを行ったり来たりして、0になった時点でreturnにジャンプだ。おお。ちゃんとwhileと同じ動作になる。

頭の中のスパゲッティ

構造体の使い方がCよりややこしいとか変数の扱いがちょっと違うとかってのもハマったけど、それはまぁ一度見てしまえばなんとなく分かる。それよりかジャンプ構文ヤバい。こんな短いコードでしかもラベル貼れるのにも関わらず「あれ、今どこ行ってんだっけ?」と何度かなったのに、「goto: 50」とかでプログラミングしてたとか信じ難いなぁ。そりゃスパゲッティも絡まるよ。ループ構文考えた人は偉大だなぁと思ったし、Rubyのイテレータとか神々しくさえ見えました。まる。

ぶっちゃけ、LLVMアセンブラを勉強するよりllvm-gccの使い方を覚えた方が手っ取り早いと思う。ちなみにllvmrubyで書くともっと楽ではあるんだけど、可読性はむしろ下がる印象。Rubyのライブラリ(Cで書かれてるRuby本体のコードの方)に依存するともう少し楽なのかもしれないけど、どっちにしろあんまりRubyっぽくないコードを書かなきゃいけなくなるし、最終的に生成されるコードの上でどういう遷移をしてるのかが分かり辛い。まぁ、でも、LLVMアセンブラ書くのが楽しくなってきちゃったのでこのまま進むことにするけどね。頭の訓練だと思ってやることにする。

ここ数日、LLVMについて少し勉強している。そもそもなんでLLVMを触り始めたかというと、Twitter上で「今コンパイル欲求に駆られている」と(割と何も考えずに)つぶやいたところ、

  1. 「じゃあDTコンパイルしようぜ」
  2. srd!
  3. でもあれコンパイラとは名ばかりでぶっちゃけ文字列をRubyコードにtranslateしてるだけだったりするね
  4. 「DTパーサを改良してLLVMにブリッジして、クロスプラットフォーム環境で高速に動作するDT処理系にするといいよ」
  5. 何その無駄に敷居高いお仕事!誰得!でもなんか面白そう!

というやりとりがあって、じゃあ本当に誰が得するのかわからないけど面白そうだからLLVMをバックエンドで使ってesotericがサポートしてるコードからバイナリを生成するコンパイラ作ろうぜ、という流れになったから。実にLLVMの無駄遣いですね。この記事ブクマするときは「LLVMの無駄遣い」ってタグを付けるといいですよ。

LLVMって何さ?

まずそもそも、iPod touchのJail Breakに手を出そうとしたときにちょこっと調べたりした(iPhoneSDK発表以前、JBしたiPod touch/iPhone向けにアプリを開発する際にはLLVMを使ってiPhone OS向けにコンパイルする必要があった。最近は追ってないので今どうなってるかは知らない)程度だったので、実のところLLVMが何をするものなのかちゃんと分かってなくて、どうすんべーとまず調べ直すところから始める。

LLVMとはLow Level Virtual Machineの略で、Lightweight Languageとは特に関係がないようだ(お約束)。知ってたよ。うん。知ってたってば。調べた結果、コンパイラ基盤と呼ばれるものでコンパイラを作るのに使うライブラリ・ツール群であること、VMの名の通り一度LLVMで処理できる中間言語にした後、それをLLVMのツールで実行したりネイティブのバイナリに変換したりして使うということ、コンパイル時や実行時に様々な最適化を施してくれて、より実行効率の良いプログラムを作れるようにしてくれるらしいこと、なんかが分かった。他にも色々あるけど、それはきっと詳しい人がどっかでまとめてくれてるから割愛。うん。分かんなかったわけじゃないよ。違うってば。

あと、llvm-gccとかclangとかを使えばC/C++/Objective-CのコードをLLVMに対応させてコンパイルできるようだ。それはそれで面白いけど今回は「自作の言語をコンパイルするのにLLVMを使う」のが目的なので、どっちかというとそれ相当のものを作ることになるのでとりあえずその辺は後で見ることにする。DTコンパイラをllvm-gccと並べてよいものかとかそこにツッコミを入れるのは無しの方向で。石を投げたりしないで下さい。

Rubyから使う

大雑把に何なのかはわかったけど、さてどう使おう。C++では使えるようだしサンプルもC++のコードが並んでるんだけど、C++書いたことないしなぁ、ってかRubyで書いてたのをC++を勉強しつつ書き直すとか面倒くさいなぁ、むしろObjC書きたいなぁObjC、とか段々脱線しはじめたときに、RubyからLLVMを使うgemがあるのを見つけた。

これこれ、これが欲しかったのよと早速gem installしてみたところ、コンパイルは通ってちゃんとインストールできるんだけど、サンプルコードを動かしてみたところdylibのload errorが出る。MacOSX10.5のRuby1.8.7(LLVM、RubyともにMacPortsからインストール)でしか試してないけど、どうも上手く行かない様子。調べてみようと思ってgithubからソース落としてきて、ローカルでgemをビルドするところからやってみたら、そっちはちゃんと動くようになった。あれかなぁ、リンクするライブラリとか違うとこ見ちゃうのかな。まあいいや、とりあえず深追いするのはもう少し後にしよう。

大雑把にllvmrubyの使い方を説明すると、大体以下の通り。

  1. LLVM::Moduleのオブジェクトを作る
  2. LLVM::Module#external_functionで外部のライブラリの関数を使えるようにする
    • CやC++のライブラリから取ってこれるようなので、Rubyの組み込み関数とかも呼べる
  3. LLVM::Module#get_or_insert_functionで関数を定義する
    • 上のメソッドがLLVM::Functionのオブジェクトを返すので、それのcreate_blockメソッドでブロック(関数の中身)を用意する
    • ブロックのBuilderを取得して、それに対してごにょごにょして中身を作る
    • b = method.create_block.builderですね
  4. LLVM::Module#write_bitcodeでコンパイルしてファイルに書き出すか、LLVM::ExecutionEngineのrun系メソッドでそのまま実行する

ちなみにこれはLLVMのバイトコードを生成する手順だけど、他にRuby1.9のVMの命令セット互換の中間表現を実行するruby_vm.rbが添付されてたり、Rubyのコードをllvmrubyを使ってJITコンパイルするものだと思われる(ちゃんと見てないので間違ってたらツッコミ歓迎)yarv2llvmってgemがあったりする。ただまぁ、「DTをRuby上で高速に実行したい」のではなくて「DTからスタンドアローンのネイティブプログラムを生成したい」ので、こっちは今回は使わない。Cでの拡張をしないアプローチでRubyのプログラムを高速化したくなったらこの辺のを使うのかな、多分。ruby_vm.rbの方は後でVMを実装するときに参考になりそうだからそのときにまた読もう。

ぐぬぬ

ここまでは何とか辿りついた。実はここまでで結構試行錯誤してるけど、まぁ何とかここまではよしとする。で、だ。ここで問題なのは、前回のバージョンアップで中間表現をRuby2Rubyで扱えるASTにしてしまったこと。何が問題かって、これのコンパイラを作るってのはつまりRubyのコンパイラを作るってことになるわけですよね。うん。…できるかっ!

そもそも言語処理系の基礎知識も何もない状態でネタで始めた言語作り、いきなりRubyのASTを処理できるコンパイラを作るとか正直敷居が高すぎるので、もう一度中間表現の見直しをすることにした。もっとシンプルなASTにしておけばコンパイラの方でも扱いやすいし、前回ぶっ殺したEsotericVMの方ももう少し楽に作れるかもしれない。

そこで今少しずつ仕様の見直しをしつつコンパイラを書きつつ進めてるのだけど、Low Level Virtual Machineと言うだけあってライブラリ側では大分コアなところしか用意はしてくれないわけですよね。てことで諸々のデータ型とか最低限必要な組み込みの関数とか自分で用意してやらなきゃいけないわけで、その辺考えてたら大分混乱してきた。

どう考えてもDTにオブジェクトシステムとかGCとかは要らないので適当に端折ろうとは思うのだけど、esotericはパーサ部分で大方の言語固有の要素を解決しちゃってコンパイラやVMの方は汎用的な言語処理系の基盤にしたいわけで、そうすると一応はちゃんと考えて設計しないといけないよなぁ。いかにミユビナマケモノとはいえそろそろノリでなんとかできる範囲を超えてきた感じ。助けてくだしあ。とりあえずお薦めの書籍とか誰か教えてくれると嬉しいなぁ。情報系の学生が読むようなの。

↑このページのトップヘ