msumimz's diary

RubyにJITコンパイラを実装する個人プロジェクトの情報発信ブログです。

開発方針について

JITコンパイルの生成元を、ASTからYARVインストラクションへ変更した話です。

JITコンパイルを行う元となる情報として、プログラムをパースした結果の構文木(AST)と、それをさらにコード化したYARVインストラクションがあります。今まではASTに基づいてCFGを生成していました。

ASTを使うことには、以下の利点があります。

  • 安定している。文法が変わらない限り、ASTが変わることはあまりありません。YARVインストラクションは最適化の対象なので、いつ変更されるかわかりません。

  • 生成されるCFGを最適化しやすい。YARVインストラクションはMRIの実行エンジンで効率的に実行できるように設計されており、JITコンパイラにとって最適とは限りません。ASTを直接変換した方が効率的なCFGを生成しやすいといえます。

  • 疎結合。ASTは文法の表現であるという意味でYARVインストラクションより抽象的であり、特定実装との結合が弱まります。将来、YARVエンジンを取り除く選択肢も生まれます。

が、ASTからですと、やはり実装がめんどくさかったです。具体的には多重代入やメソッド引数の取り扱いで、これらのCFGをASTから生成するのは大変で、また互換性が維持できているのか確信を持てませんでした。

というわけで妥協しまして、YARVインストラクションからCFGを生成することにします。YARVインストラクションは、多重代入などの難しいところを単純な命令列に解決してくれていますので、実装が楽になります。インストラクションの種類は100弱ありますが、最適化のため細分化されており、同種の命令が多数あるので、見た目ほど多くはありません。

これで作業量が相当減りますので、現在の遅々としたペースでも完成までこぎつけられるのではないかと期待しています。

定数を実装しました

定数を実装しました。

module Outer
  class C
    X = 10
  end
end

def m
  Outer::C::X
end

Jit.precompile Object, :m

puts m   # => 10

定数の値はコンパイル時に展開されます。定数の再定義やオートロードにも対応しています。

class_eval辺りと組み合わせると問題が起きるかもしれません。eval系メソッドの取り扱いは、ブロックを実装するときに合わせて考えようと思います。

実装していて気付いたのですが、Rubyでは

nil::C

という書き方ができて、

C

と同じ意味になるのですね。Rubyにありがちですが、たまたま実装の都合でできてしまっているのか正式の文法なのかよくわかりません。自分のコードでは使わない方がよさそうです。

Visual Studio 2013に移行します [追記あり]

今まではVisual Studio 2010でもコンパイルできるように書いていたんですが、少しずつVisual Studio 2013に移行しようと思います。

移行によって、主にC++11の機能で使えるものが増えます。詳細なリストはC++11 の機能 (Modern C++) のサポートにありますが、特に

  • Initializer list
  • Range-based for

が使えるようになります。

移行の理由は、先日LLVMのtrunkのソースコードを眺めていたら、Range-based forを使っているところを見つけてしまったためです。どうやらLLVMプロジェクトでは、今後はC++11の機能を積極的に使っていくそうです。

ビルド環境を制限するのはよくないと思って今まで頑張ってきたのですが、次期LLVMのビルドに最新のコンパイラが必要になる以上、こちら側だけ頑張っても仕方ありません。*1

g++/clangのC++11対応はVisual Stduioよりずっと進んでいますので、他環境での互換性で問題になることはありません。また、Visual Studio 2013でもWindows XPで動くバイナリをビルドすることが可能です。

[追記]
実際に試してみたところ、最新のLLVM 3.4.2はVisual Studio 12までしかサポートしてませんでした。Visual Studio 13はもうリリースから1年近くたつのですが。

せっかくなので、LLVM 3.4からLLVM 3.4.2へのアップデートを試みたところ、#include <cxxabi.h>(gcc specificなヘッダファイル)などをインクルードしていてVisual Studioでビルドできないようです。

よく見ると、LLVM 3.4.2の公式ダウンロードページLLVM Download Pageに、Windows版のバイナリがありません。LLVM 3.4.1まではあるのに…。これって、Windowsでビルドできないことを知りながらリリースしたってことですかね。

うへえ。

*1:どうせこちらの正式リリース前に次期LLVMがリリースされるだろう…という情けない前提です。

README.mdを書きました

いんちき英語でREADME.mdを書きましたので、Githubにプロジェクト概要とインストール手順が表示されるようになりました。

https://github.com/msumimz/ruby/tree/rbjit

合わせて、JITモジュールを定義して、precompileメソッドをモジュール関数にしています。

従来:

precompile Object, :m

これから:

Jit.precompile Object, :m

Jitという短いモジュール名が他とかぶっていないか心配ですが、Ruby toolboxで検索しても同名プロジェクトがなかったので大丈夫でしょう。

これで、フルRubyのビルドに対応しました - msumimz's diaryの「今後の予定」で記載した事項は、Linux対応を除きおおむね対応したことになります。*1

そこで、次のステップとして、言語機能の実装に取り掛かろうと思います。

ガイドとして、Computer Language Benchmarks Gameソースコード及び、このサイトで使われているコードの古いバージョン?と思われる、rubyソースツリーのbenchmark/bm_so_*.rbを使いたいと思います。これらのベンチマーク用プログラムが動作することを目標に、言語機能を実装していきます。

*1:あの複雑怪奇なMakefileの森に再び分け入る気力が出ないため、Linux対応は後回しにします。

メソッドの再定義に対応しました

メソッドが再定義された場合に、JITコンパイルされたメソッドが正しく動作するための仕組みを導入しました。

この仕組みはさまざまな実装方針が考えられ、実行速度・メモリ使用量・コンパイル速度・実装の容易さの間でトレードオフがあります。

とはいえ、実装の良し悪しはベンチマークをとって判断するべきであり、まともなベンチマークが動かない状態で悩んでもしかたありません。そこで、今回は比較的実装が容易な方法にしています。

こんなコードや、

def inlined
  3
end

def m
  inlined
end

precompile Object, :m  # 型解析され、inlinedがインライン化される

puts m   # => 3

def inlined  # inlinedを再定義する
  5
end

puts m   # => 5

こんなコードが正しく動くようになります。

def m(a, s)
  a += 1
  eval s  # 任意のコードが実行される
  a += 2
end

具体的な実装についてはいつか記事にするかもしれません。

precompileのエラーチェックをちゃんとしました

こんなコードを実行すると

def m)
  [1,2,3]
end

precompile(Object, :m)

こんなエラーになります(配列リテラルをサポートしていない)。

$vc10/Debug/miniruby test.rb
test.rb:5:in `precompile': m:2: Node type NODE_ARRAY is not implemented yet (ArgumentError)
        from test.rb:5:in `<main>'

今まではクラッシュしていました。今までがひどすぎたという話ですが…。

これで、利用者がいろいろなコードに対して試しやすくなるのではないかと思います。