type t (* void *)

ソフトウエアのこととか

コンパイラ: JVMバイトコードへのコンパイル

言語処理系 Advent Calender1日目の記事です。 初日なのであまりハードルを上げすにライトなネタを。

趣味でコンパイラを作る際に最終的な出力ファイルを何にするのかは悩みどころです。
手づくりの温かみのあるバックエンドでやるのか、LLVMやC--、COINSを経由するのか、 はたまたJVMバイトコードなどのバイトコードにするのか。 CやJavaScriptに出力するのは相対的に簡単そうで実用的だなぁという感触もあります。

今回はそれなりの言語をちゃちゃっと走らせるための対象プラットフォームとしてJVMを検証するために、 min-camlのサブセットのJVMバックエンドを実装してみました。
サブセットと言っているのはクロージャの対応が終わってないからです。実装の見通しは立ってます。 感想としてはJVMバイトコードへのコンパイルはそれほど難しくないけども JVM特有のつらみがあるという知見が得られました。

1日目ということでJVMバイトコードの説明や、 スタックマシンへのコンパイルについて書きたいと思います。 min-camlに移植した話は別の記事ということで……間に合わなかったとも言いますがが。
詳しくない人が読むことを期待して結構真面目に基本的な部分から書きます。

JVMバイトコードについて

JVMはスタックマシンですが、純粋なスタックマシンではなく 無限のローカル変数をストアしたりロードするための機能があります。 なのでこのマシンへのコンパイルはとても簡単です。

ちなみに別に.javaファイルを最終結果として出力しても良いのですが その場合gotoが使えません。末尾再帰最適化をしたくなったら直接バイトコードを吐かねばなりません。 Compiling standard ML to Java bytecodes ではSMLをJavaバイトコードコンパイルしていますが末尾呼び出し最適化のためにgotoを用いたと書かれています。 (そのために分割コンパイルできなくなったんだと思いますが……)

スタックマシンというのは木構造をほぼそのままコンパイルしやすい構造です。 基本的なアイディアは、再帰的にコンパイルする関数compを定義しcomp tの出力する命令列を実行すると、 評価結果1つだけがスタックにプッシュされるように設計することです。
この不変条件だけを意識すれば非常に簡単です。簡単な場合の

  • 四則演算の場合
  • 関数呼び出し(スタティックメソッド呼び出し)の場合
  • ローカル変数がある場合

について考えてみます。

四則演算

例えば(- t1 t2)コンパイルする場合を考えてみましょう。 整数同士の引き算を行うための命令isubは スタックの上から2番目の値とスタックトップの値をポップして、2つの差を取って スタックにプッシュする命令です。スタックの動きを表してみると

..., i1, i2     ->
..., (i1 - i2)

という動きになります。(一番右がスタックトップ、矢印が実行したあとだという気持ちです) 詳しくはリファレンスを見てください。 Wikipediaの記事の表も見やすいと思います。

ちなみに命令の接頭辞のiintを表していて、接頭辞l(long)やf(float)、d(double)、a(ポインタ) も存在します。

t1の評価結果1つだけをプッシュするようにコンパイルし、 同様にt2の評価結果1つだけをスタックにプッシュするようにコンパイルして、 最後に引き算を実行するようにします。Haskell風に書くならば(文法は適当です型とか考えてません)

comp :: prog -> instruction []
comp (- t1 t2) = comp t1 ++ comp t2 ++ [isub]

でしょうか。これを実行すると comp t1, comp t2により2つの整数がスタックトップに追加され、 その2つの値をポップした後、その2つの値の差をとったものがスタックにプッシュに追加されます。
更にこれは上で述べたcomp (- t1 t2)の出力は実行結果1つだけを スタックトップに追加する、という不変条件を守っています。

四則演算は他のものもこれと全く同様です。

関数呼び出し

関数呼び出し(スタティックメソッド呼び出し)のためには invokestatic命令があります。これはn引数関数(スタティックメソッド)を実行するときに スタックトップからn個の値をポップして引数として渡して実行結果をスタックにプッシュする、というものです。

..., v1, v2, ..., vn  ->
..., f (v1, v2, ..., vn)

この方針でcompを関数適用の場合でも実装してみると、例えば f (t1, t2, ..., tn)は引数部分の木を順番にコンパイルして結合し、最後にfを呼べばいいことがわかります。

comp (f (t1, t2, ..., tn)) = 
  comp t1 ++ comp t2 ++ ... ++ comp tn ++ [invokestatic f (typeof f)]

ちなみにinvokestatic命令には一緒にメソッドの型を書きます。
JVMの場合は書かないとオーバーロードがあるのでどのメソッドを呼び出すのか分からないですし、 何個引数を消費するのか、またスタックに載っている値の長さは揃っていないので (int型は32bit, long型は64bit)どれくらいの長さをパラメータとして渡すのかも分かりません。

ローカル変数

iload nはスタックにn番目のローカル変数をプッシュする命令です。
istore nはスタックトップの値をn番目のローカル変数に代入しポップする命令です。

let x = t1 in t2

のようなプログラムは以下のようにコンパイルできます。

comp (let x t1 t2) = comp t1 ++ [istore n] ++ comp t2 (ただしnはフレッシュ)

comp t1の出力を実行すると値が一つだけスタックに追加されるので、次にistore nを実行すると その値がn番のローカル変数として保存されます。そしてcomp t2の出力を実行するので このコンパイル結果を実行してもスタックに1つだけ値がポップされることが分かります。

上のような例を考えてみると、変数を使うためにコンパイル途中に変数がドコに入っているのか 覚えておく必用があることが分かります。
変数自体のコンパイルは変数が格納されている場所を覚えておいてiload nなどその型にあった ロード命令を呼ぶだけです。

comp (x) = [iload n] (ただしnはxが格納されている番号)

またiloadistoreの最初についているiisubと同じくintを表しており、 longdouble、ポインタをロードするバージョンも存在します。

具体例

Javaコードをコンパイルしてそれをjavapコマンドで逆アセンブルしてみましょう。 javap -c -s Hogeの実行結果は以下のようになります

プログラム(それ以外省略):

public static int f (int x, int y)
{
    return x + M.f (3 * y, M.g (4));
}

実行結果:

public static int f(int, int);
    Signature: (II)I
    Code:
       0: iload_0
       1: iconst_3
       2: iload_1
       3: imul
       4: iconst_4 
       5: invokestatic  #2                  // Method M.g:(I)I
       8: invokestatic  #3                  // Method M.f:(II)I
      11: iadd 
      12: ireturn
  • iconst_n命令はスタックに整数nをプッシュします
  • ireturn命令はスタックトップの値をポップして返り値とし、呼び出し元に戻る

一応1命令ごとのスタックの実行イメージ図を貼っておきます。

f:id:no_maddojp:20151130170031j:plain

上のプログラムを中置演算子をすべて前置にしてcompでの変換を考えてみると

comp (+ x (M.f [* 3 y, M.g [4]])) 
= comp x ++ comp (M.f [* 3 y, M.g [4]]) ++ [iadd]
= [iload_0] ++ comp (* 3 y) ++ comp (M.g [4]) ++ [invokestatic M.f] ++ [iadd]
= [iload_0] ++ comp 3 ++ comp y ++ [imul] ++
    comp 4 ++ [invokestatic M.g] ++ [invokestatic M.f] ++ [iadd] 
= [iload_0, iconst_3, iload_1, imul, iconst_4, invokestatic M.g, invokestatic M.f, iadd]

ireturnを補ってやれば全く同じ出力になりました! やや読みづらいかもしれませんが、やっていることは本当に1つ1つ展開しているだけです。 落ち着いてノートにご自分で展開してみてください。

Javaのような言語ではトップレベルにいきなり式を書くことはできず returnやassign, void型のメソッド呼び出しであることが簡単にわかるのでireturnなども補うことができます。

JVMバイトコードには他にもif文のための命令や配列操作、キャストなどもありますが 最適化などを考えなければcompの実行結果の不変条件をきちんと守ればそんなに難しくはありません。

Jasminでバイトコード手書きする

直接JVMが解釈できるバイナリを書くのも難しくないと思いますが デバッグがつらそうなのでアセンブラを経由して出力させましょう。
僕はよくわからないですがJasminアセンブラとしてそれなりに使われているようです。

Debian 8のstableレポジトリから普通にaptでインストールしたものはなんだか ヒープ使いきって死んだりするのでforge からダウンロードするといいですサンプルもついてきますし。

jasminの使い方はどうやらいろいろな大学で教材として使っているようで なんだかたくさんヒットします。 マニュアルのリファレンスとサンプルだけでも十分に理解できますが、 このへん を見るといいと思います。

jasminに限らずJVMバイトコードを出力するときに気をつけることは、 javaコマンドで実行するときにベリファイヤがバイトコードの型検査のようなものをするということです。
例えば実態がIntegerだと明らかにわかっているObject型の値から メソッドintValueを呼ぼうとするとcheckcast typ命令でキャストを行わない限り ベリファイヤが不正なバイトコードだと言って実行させてくれません。

-noverifyオプションをつけると検査無しで実行できるのでベリファイエラーになったらば一度 検査無しで実行してみるといいと思います。 どの命令で失敗したのかなどあまり親切なメッセージを出してくれないところがあれですが コンパイラ開発者にしか関係ないことですからね……。

おまけ

EmacsVM向けのバイトコードもバックエンドとして検討していました。 elispコードはバイトコードコンパイルされますがこれもスタックマシンベースです。

elispバイトコードの関連だと、 ちょっとだけ検索してみると面白い記事がヒットします。

Emacsにはdisassembleコマンドがあり、Emacsが読み込んだバイトコードを表示できます。 下のプログラムをファイルに保存してbyte-compile-fileload-fileで読み込んでから disassembleを実行してみます。

;;; -*- lexical-binding: t -*-
(defun f (x y)
  (+ x y)
  )

(defun fact (n)
  (if (= n 0) 1 (* n (fact (- n 1))))
  )

実行結果はこちら

byte code for f:
  doc:   ...
  args: 514
0       stack-ref 1
1       stack-ref 1
2       plus
3       return

byte code for fact:
  doc:   ...
  args: 257
0       dup       
1       constant  0
2       eqlsign   
3       goto-if-nil 1
6       constant  1
7       return    
8:1     dup       
9       constant  fact
10      stack-ref 2
11      sub1      
12      call      1
13      mult      
14      return    

JVMと違いローカル変数という概念はelispバイトコードにはありません。 fバイトコードを見てみると引数はスタックに格納されてから関数呼び出しされることがわかります。
stack-ref nはトップからn番目の値をコピーしてプッシュする、というものです。
0-basedな数え方をするのでstack-ref 1は上から2番目の値(fの最初のバイトコードならばxを指す) をコピーすることになります。次のstack-ref 1xが積まれたのでyを指します。

あとはJVMバイトコードが理解できれば特に難しい部分はないのですが、 関数呼び出しの際に関数もpushして関数呼び出しを行います(fact関数の中の9命令目のconstant fact)。

ちなみにlexical-scopeにするオプションをつけてコンパイルすると 引数はスタックに格納されて渡されますが、つけないと名前でアクセスすることになります。

byte code for f:
  args: (x y)
0       varref    x
1       varref    y
2       plus      
3       return    

このくらいにしておきますがなんだかスタックマシンとして普通なので このあたりを読めばわかります。

http://www.emacswiki.org/emacs/ByteCodeEngineering