\chapter{CbCによるMoarVM}
\section{スクリプト言語のバイトコード}
プログラミング言語処理系は一般的に、 コンパイラ又はインタプリタに、 対象のソースコードを入力として与える。
処理系はソースコード中の各文字列を、 トークンと呼ばれる形式に変換する。
トークンは処理系によってはオブジェクトそのものなどに変換される。
このトークンに変換するフェーズを字句解析と呼ぶ。
変換されたトークンが、 対象のプログラミング言語の文法などに沿っているかどうかの確認を行う。
文法に沿っていた場合、 文法に応じてトークンを木構造に変換する。
これを構文解析と呼ぶ。
構文解析の後は、 素朴なインタプリタ言語と呼ばれる種類のプログラミング言語の場合、 これらを木構造の根から順次実行する。
この処理の流れを図\ref{fig:not_use_bytecode_Sample_generally_lang}に示す。
直接構文木を実行する場合、 実装そのものは単純になるが、 処理時間などが非常にかかるなどの特徴がある。

\begin{figure}[ht]
\caption{構文木を直接実行するプログラミング言語の処理の流れ}
 \begin{center}
  \includegraphics[width=120mm]{./fig/not_use_bytecode_sample_generally_lang.pdf}
 \end{center}
 \label{fig:not_use_bytecode_Sample_generally_lang}
\end{figure}

現在の主流なスクリプト言語は、 一旦変換した構文木をバイトコードと呼ばれるバイナリ形式に変換する。
バイトコードを利用する種類のプログラミング言語の、 処理の流れを図\ref{fig:bytecode_Sample_generally_lang}に示す。
この場合、 入力されたソースコードをバイトコードに変換する実装と、 変換されたバイトコードを評価する仮想機械に処理系が分けられる。
仮想機械はOSのエミュレータではなく、 プロセス仮想マシンと呼ばれるものである。
バイトコードを直接出力できる形式のプログラミング言語にJava、 Javaの仮想機械にJVMが存在する。
内部的に利用しており直接は出力されない言語に、C言語で実装された MRIと呼ばれるrubyの実装などがあり、 この仮想機械にYARVが存在する。
バイトコードを経由することで、 コンパイルを担当する実装と、 評価を担当する仮想機械の実装に分類する事が可能となり、 それぞれに適した最適化処理が実装可能となる。
また実行する際の速度もバイトコードを経由することで上昇する。

\begin{figure}[ht]
\caption{バイトコードを使用するプログラミング言語の処理の流れ}
 \begin{center}
  \includegraphics[width=120mm]{./fig/bytecode_sample_generally_lang.pdf}
 \end{center}
 \label{fig:bytecode_Sample_generally_lang}
\end{figure}

RakudoではPerl6、 NQPがそれぞれ対象のVMのバイトコードを生成し、 そのバイトコードをVMが実行する。
バイトコード生成までの処理をフロントエンドと呼び、 バイトコードから評価を行う処理をバックエンドと呼ぶ。
これらはJavaの様にバイトコードを出力する事も可能であるが、 オプションで指定しない限りは、 rubyなどの様に内部的にのみバイトコードを利用する。
主にRakudoで利用されている仮想機械にC実装のMoarVMがあり、 本研究ではMoarVMのバイトコード評価部分について検討をする。

\section{MoarVMのバイトコード}
CbCでMoarVMを書き換える際に、 いきなり全てを実装する事は難しい。
スクリプト言語の処理系の中心は、 与えられたバイトコードから実際の処理を逐次実装する部分である。
その部分をバイトコードインタプリタと呼ぶ。
今回はMoarVMの書き換えを検討する為に、 まずMoarVMのバイトコードインタプリタ部分の書き換えを行う。
書き換えを行うにあたり、 MoarVMのオリジナルの箇所の実装を確認する。
今回対象とするMoarVMのバージョンは2018.04.01である。

MoarVMのバイトコードは、 フォーマットが決まっており、 複数の意味のあるバイトコードの集合となっている。
今回は、MoarVMの命令を実行する際に必要な、 命令コードに対応するバイトコードの部分に着目する。
これは、 今回書き換えを検討するMoarVMバイトコードインタプリタが読み込み、 評価するバイトコードの部分が、 命令コードバイトコードに対応する為である。
MoarVMのバイトコードの中の、 命令に対応するバイトコードの構成を図\ref{fig:bytecode_segment}に示す。

\begin{figure}[ht]
\caption{MoarVMの命令バイトコード}
 \begin{center}
  \includegraphics[width=120mm]{./fig/bytecode_segment.pdf}
 \end{center}
 \label{fig:bytecode_segment}
\end{figure}


MoarVMの命令バイトコードは16ビットである。上位8ビットが、 バンクと呼ばれる命令セットの指定となる。
MoarVMの命令はバンクの0から127番までが、 MoarVMのコア機能となっており、 128から255番までが、 拡張可能な命令セットとなっている。
下位8ビットは、 バンクの内部の命令指定となっている。
命令によっては、 この後のバイトコードで0個以上のオペランドを必要とする物がある。
オペランドの中にはレジスタの型指定、 引数などが埋め込まれ、 命令バイトコードとの対応のために16ビットで表現される。

Perl6のサブセットであるNQPは、 NQPソースコードとMoarVMバイトコードの変換の対応を見る事が出来る。
これはNQPのインタプリタである小文字のnqpは、 MoarVMバイトコードを出力する事が可能であり、 出力されたバイトコードはMoarVMの実行バイナリであるmoarでダンプする事が可能である為である。
実際にソースコード\ref{test_nqp}に示す簡単なNQPサンプルコードを作成した。

\lstinputlisting[frame=lrbt, label=test_nqp, caption=2引数の加算とインクリメントを行うNQPサンプルコード]{./codes/add.nqp}

このコードは test\_funcというサブルーチンを定義し、 int型引数leftとrightを受け取る。
leftとrightを足した結果を、 変数sumに束縛する。
3行目でsumの値をインクリメントし、 その値を返り値として渡している。

サブルーチンtest\_funcはソースコード中の8、 9行目でそれぞれ1と9に設定した変数test1とtest2を渡している。
サブルーチンの返り値はsay関数で表示する。

このスクリプトをバイトコード化したものをディスアセンブルの様にダンプしたものを示す。

\begin{figure}[ht]
\caption{NQPソースコードとMoarVMバイトコードの対応}
 \begin{center}
  \includegraphics[width=120mm]{./fig/code_to_bytecode.pdf}
 \end{center}
 \label{fig:bytecode2code}
\end{figure}

\section{オリジナルのMoarVMの処理}

MoarVMのバイトコードインタプリタはsrc/core/interp.c中の関数 MVM\_interp\_runで定義されている。
この関数ではMoarVMのバイトコードの中の、 命令に対応するバイトコードを解釈する。
関数内では、 解釈するべきバイトコード列が格納されている変数 cur\_op や、現在と次の命令を指し示すop、 命令に対して受け渡す現在のVM情報であるThreadContex tcなどが変数として利用されている。
実際に命令ディスパッチを行っている箇所の一部をソースコード\ref{origin_dispatch}に示す。

\lstinputlisting[frame=lrbt, label=origin_dispatch, caption=オリジナルのMoarVMの命令ディスパッチ部分]{./codes/src/dispatch.c}

ソースコード\ref{origin_dispatch}中のOP(.*)と書かれている部分が、 それぞれのバイトコードが示す命令名となっている。
例えばno\_opは、 何もしない命令であるため、 マクロNEXTを利用しプログラムカウンタ相当のcur\_opを進めるのみの処理を行う。
また登場する DISPATCH や OP 、 NEXT などはそれぞれマクロとして定義されている。
これらMoarVM\_interp\_run中で、 利用されるマクロの定義を、 ソースコード\ref{origin_dispatch_macro}に示す。

\lstinputlisting[frame=lrbt, label=origin_dispatch_macro, caption=オリジナルのMoarVM\_interp\_runで使用されるマクロ]{./codes/src/orig_macro.c}

このマクロの中では、 利用しているCコンパイラがラベルに対してのgotoが利用できるコンパイラ拡張を実装している場合は MVM\_CGOTOが真となり、 6行目までが実行される。
それ以外の場合は8行目以降のマクロ定義となる。
ラベルgotoが利用できる場合、 マクロDISPATCHは空白として設定され、 マクロOPは、 それぞれの命令に対応したラベルとなる。
この場合の処理の流れを図\ref{fig:origin_label_goto}に示す。

\begin{figure}[ht]
\caption{ラベルgotoが利用できる場合のオリジナルのMVM\_interp\_runの処理の流れ}
 \begin{center}
  \includegraphics[width=50mm]{./fig/origin_label_goto.pdf}
 \end{center}
 \label{fig:origin_label_goto}
\end{figure}

次の命令に移動する際は、 マクロNEXT\_OPを用いてcur\_opを次の命令に移動させ、 opの値を再設定する。
このopが実行すべき命令の番号が格納されている。
opを用いて、ソースコード\ref{labels_list}に示す配列LABELSから、 命令に対応するラベルを取得する。
LABELSはマクロOPが変換したラベルのリストである。
ソースコード\ref{origin_dispatch}の場合、no\_opはopが0が代入され、 const\_i8は1が設定されている。


\lstinputlisting[frame=lrbt, label=labels_list, caption=MoarVMの命令ラベルが設定されている配列]{./codes/src/oplabels.h}

ラベルgotoが利用できない場合、 マクロDISPATCHはswitch文に、 OPはcase文にそれぞれ変換される。
cur\_opは数値そのものである為、 この場合はラベル配列へのアクセスは行われない。
case文に変換された場合の処理の流れを\ref{fig:origin_not_use_label_goto}に示す。

\begin{figure}[ht]
\caption{case文に展開された場合のオリジナルのMVM\_interp\_runの処理の流れ}
 \begin{center}
  \includegraphics[width=70mm]{./fig/origin_not_use_label_goto.pdf}
 \end{center}
 \label{fig:origin_not_use_label_goto}
\end{figure}

またソースコード\ref{origin_dispatch}の中に含まれているマクロGET\_REGは、 ソースコード\ref{get_reg_c}に示す定義がされている。

\begin{lstlisting}[frame=lrbt,label=get_reg_c,caption=レジスタ情報を取得するマクロGET\_REG]
#define GET_REG(pc, idx)    reg_base[*((MVMuint16 *)(pc + idx))]
\end{lstlisting}

配列reg\_baseはMoarVM上で利用される、 MoarVMのレジスタのリストである。
このマクロ中のpcは、 MVM\_interp\_run上ではcur\_opとなっている。
idxは命令ごと個別に設定しており、 例えばconst\_i64内で利用されている GET\_REGは、 idxの値が0に設定されている。
これはMoarVMがレジスタ情報を取得する際に、 命令を基本に前後に参照できるレジスタを指定出来る為である。
参照しているレジスタ集合の変数reg\_baseは、 MVM\_interp\_run中ではローカル変数として宣言されている。


MoarVMのディスパッチ部分は、case文に変換される可能性がある。
従って、 MoarVMの命令コードに対応する処理は、 Cソースファイルの特定の場所に記述せざるを得ない。
この方法の場合、命令コードに対応する処理のファイル分割などのモジュール化が行えず、 1ファイル辺りの記述量が膨大になってしまう。

\section{CbCによるMoarVMの実装}
interp.c内のMVM\_interp\_runでは、 命令コードのディスパッチはマクロを利用したcur\_opの計算及びラベルgoto、 もしくはマクロDISPATCHによるswitch-case文で行っていた。
このディスパッチ方法では、 case文を利用する可能性があるため、 ファイルが冗長になる事や、 モジュール化が出来ないという問題が生じる。

CbCによって書き換えを行ったMoarVMである、 CbCMoarVMではこの問題を解決する為に、 CodeGearの概念を導入する。
まず、 MoarVMの命令に対応するCodeGearを作成し、 各CodeGearの名前を要素として持つCbCのCodeGearテーブルを作成した。
CodeGearのテーブルは、 特定のcbc\_nextというCodeGearから参照する。
cbc\_nextから命令ごとのCodeGearに遷移し、 命令に対応する処理をした後に、 cbc\_nextに戻り、 別の命令に対応するCodeGearに遷移を繰り返す。
このcbc\_nextは、 元のMVM\_interp\_runで使用されているマクロNEXTを、 CodeGearで書き直したものである。
実際に書き直したマクロ及び、 cbc\_nextをソースコード\ref{cbc_next}に示す。


\lstinputlisting[frame=lrbt, label=cbc_next, caption=cbc\_next及びCbCMoarVMでのマクロ例]{./codes/src/cbc-interp-next.cbc}

CodeGear間の軽量継続を中心に設計している為、 switch case文を利用するマクロは削除した。
また各マクロの引数に変数iを導入している。 
 変数i は、 バイトコードインタプリタ内で利用する、 MoarVMのレジスタ情報などが格納された、 構造体へのポインタである。
iが示す構造体INTER、 呼び i の型である構造体INTERPは、 ソースコード\ref{cbc_inter}の示すように宣言している。
これは、マクロ内部で現在の命令を示すopや、 命令列 cur\_op にアクセスする必要があるが、 従来のマクロの記述ではCbCを利用した場合に、変数にアクセス出来なくなる為に導入している。

\lstinputlisting[frame=lrbt, label=cbc_inter, caption=MoarVMの情報を格納した構造体INTER]{./codes/src/INTERP.h}

\section{命令実行箇所のCodeGearへの変換}

命令実行箇所は、 case文又はラベルgotoで移動した先に記述されている。
これらの箇所を、 それぞれ専用のCodeGearに変換することで、 命令の実行をCodeGearの遷移としてCbCを利用して実装する。
MVM\_interp\_runでは、 ソースコード\ref{origin_dispatch}中で示すとおり、 マクロOPを用いて記述されている。

OPを用いて記述しているそれぞれの命令は、 通常ソースコード\ref{labels_list}に示すラベル配列、 またはswitch case文で遷移する。
従来はソースコード\ref{origin_dispatch_macro}に示す、 変数opの値利用してをマクロNEXTで対象の命令のラベル、 およびswitch文に値を引き渡す処理をしていた。
CodeGearでの実装の際も、 このインターフェイスに揃えて実装する。
変数opの数値は、 ソースコード\ref{labels_list}に示すラベル配列の、 命令の登場順と対応している。
その為命令を変換したCodeGearをラベル配列と順序を対応させ、 CodeGearの配列を作成する。
順序さえ対応させれば、 CodeGearの名前などは問わない。
実際に作成したCodeGearのリストをソースコード\ref{codegear_list}に示す。
変換したCodeGearは、それぞれCodeGearであることを示す為、 接頭辞としてcbc\_を付けている。

\lstinputlisting[frame=lrbt, label=codegear_list, caption=CodeGear配列の一部]{./codes/src/oplables-cbc-codes.h}

変換された各命令に対応するCodeGearの一部を、 ソースコード\ref{cbc_interp}に示す。
このCodeGearはソースコード\ref{origin_dispatch}と対応している

\lstinputlisting[frame=lrbt, label=cbc_interp, caption=CbCMoarVMのバイトコード命令に対応するCodeGear]{./codes/src/cbc_codesegs.cbc}

各CodeGearは入出力として構造体INTERのポインタを利用する。
これは、各命令の中で使用している cur\_op や tcなどの変数へのアクセスの為である。
通常のMoarVMの場合、 MVM\_interp\_runの関数内でタグgotoや、 switch文を利用する為に、 MVM\_interp\_runのローカル変数に各命令処理の中でアクセスする事が可能である。
しかし、 CbCMoarVMの場合、 MVM\_interp\_runから軽量継続を利用し、 CodeGearに遷移してしまう為、 これらローカル変数にアクセスできない。


作成したCodeGearのリストCODESは、 ソースコード\ref{cbc_next}に示すとおり、 cbc\_nextというCodeGearのみが取り扱う。
cbc\_nextはマクロNEXTを利用しているが、 マクロNEXTはCODESにアクセスし、 対象となるCodeGearの名前を取得する。
CodeGearを取得後、 引数としてiを渡しgoto文によって命令ごとのCodeGearに遷移する。

命令ディスパッチに関するCodeGearの状態遷移図を図\ref{fig:dispatch_cbc}に示す。

\begin{figure}[ht]
\caption{CbCMoarVMの命令バイトコードディスパッチの状態遷移}
 \begin{center}
  \includegraphics[width=120mm]{./fig/cbc_next.pdf}
 \end{center}
 \label{fig:dispatch_cbc}
\end{figure}

図中の破線部分は通常のC言語の関数呼び出しが行われる。
CodeGearからCの関数呼び出しの返り値を利用することなどは通常のC言語と同様に可能である。
各命令に対応したCodeGearは、 cbc\_next から遷移し、 処理を行った後 cbc\_next にgoto文で軽量継続する。

また、 変換した命令の中には switch case文での、 breakが発生せず、 次のcase文に移行する命令が存在する。
各CodeGearは1命令に閉じてしまっている為、 cbc\_next ではなく、 明示的に次に次のCodeGearを指定する必要がある。
今回は直接 CodeGear 中に遷移先のCodeGearをgoto文を付けて記述した。
ソースコード\ref{cbc_interp}中では、 cbc\_const\_i8などが該当する。


命令の数は膨大である為、 全てを手作業で変換するのは望ましくない。
本研究ではPerlスクリプトを用いて、 interp.c から命令をCodeGearにそれぞれ変換し、 CodeGearのリストを自動的に作成するスクリプトを作成した。
このスクリプトは以下の修正手続きを実行する。


\begin{itemize}
  \item OP(.*)の.*部分をCodeGearの名前として、  先頭にcbc\_をつけた上で設定する。
  \item cur\_opなど、 構造体INTERのメンバ変数は、 ポインタiから参照するように修正する。
  \item GC対策のためマクロMVMROOTを利用している箇所は、 一度ダミーの関数を経由する。
  \item 末尾のgoto NEXTをgoto cbc\_next(i)に修正する。
  \item case文で下のcase文に移行する箇所は、 case文に対応するCodeGearに遷移する様にgoto文を付け加える。
\end{itemize}

この中の MVMROOT をソースコード\ref{MVMROOT}に示す。

\begin{lstlisting}[frame=lrbt,label=MVMROOT,caption={MVMROOTの定義}]
/* Macros related to rooting objects into the temporaries list, and
 * unrooting them afterwards. */
#define MVMROOT(tc, obj_ref, block) do {\
    MVM_gc_root_temp_push(tc, (MVMCollectable **)&(obj_ref)); \
    block \
    MVM_gc_root_temp_pop(tc); \
 } while (0)
\end{lstlisting}

MVMROOTは、 行いたい処理の前後で、MVM\_gc\_root\_temp系統のpushとpopのスタック操作の関数を実行する。
これは、 MoarVMが所持しているガベージコレクションに、 行いたい処理の間にオブジェクトが回収されるのを防ぐための処理である。
ガベージコレクションの回収を防ぐために、 MVM\_gc\_root\_temp\_pushでは、 大域変数の配列に一時的にオブジェクトのアドレスを入れる。
このオブジェクトは、 CodeGear中のローカル変数であるが、 CodeGear中のローカル変数は通常別のCodeGearに移動する際に破棄する為、 この様な動きを想定していない。
その為、 MVMROOT を呼び出す処理の場合は、 MVMROOT を使う命令を別の関数でラップし、 CodeGearから関数呼び出しの形で命令を呼び出す。



\section{MoarVMのデバッグ}
CbCで書き換えたMoarVMであるCbCMoarVMは、 現在gcc、 LLVM/clang上に実装しているCbCコンパイラでビルドする事が可能である。
また、 それぞれO3までの最適化オプションをビルド時に指定してもビルドする事が可能である。

MoarVMの書き換えに伴って、 正常にオリジナルのMoarVMと同じ振る舞いをするか確認をしたい。
MoarVM自体には現在テストコードが存在しない。
MoarVMのリポジトリ内のメッセージには、MoarVM上で動作するNQP、 及びRakudoに付随しているテストコードで、 MoarVMの実装をテストする事が推奨されている。
NQPやRakudoのテストは、 ソースコード\ref{cbc_test_nqp}に示す様なコードを利用する。
実際にNQPとPerl6のインタプリタとしてビルドした、 nqpやperl6コマンドを実行する。
実行時に出力された結果と、 期待する結果が一致するかを確認する方式である。

\lstinputlisting[frame=lrbt, label=cbc_test_nqp, caption=NQPのテストコードの例]{./codes/test.nqp}

NQPやRakudoのテストを行うには、セルフビルドしたそれぞれのインタプリタであるnqp、 perl6を作らなければならない。
しかし、 これらをビルドする際にはMoarVMの実行バイナリである moar を動かす必要がある。
nqpなどのビルド時には、 入力として与えられたバイトコードを解析し、 命令部分をディスパッチするバイトコードインタプリタを使用せざるを得ない。
今回はバイトコードディスパッチ部分を書き換えた為、 この部分にバグが生じていると、 そもそもnqpやperl6を生成する事が出来ない。
その為、 利用したいnqpやperl6のテストコードを出力を通して確認する事が出来ない。
従って今回はMoarVM自体にバイトコードを入力として与え、 期待する動作をするかどうかを独自に確認する必要がある。


\section{CbCMoarVMのデバッグ}
CbCMoarVMが正常にバイトコードを実行しているかどうかは、 正常に動くオリジナルのMoarVMと、 実行したバイトコードの差分を検知することで確認する事が可能である。
入力として与えたスクリプトは常に同じバイトコードに変換されると考えられるが、 MoarVMはバイトコードにUUIDの様な物を埋め込んでしまう為、 同じファイルを与えても生成されるバイトコードが異なってしまう。
その為、 NQPインタプリタのREPLの様な機能を使い、 それぞれのVMが同じ命令から処理を開始する様に調整する。

差分は、 バイトコードインタプリタのMVM\_interp\_runのソースコード中で、 次の命令を計算する箇所で、 命令に対応する数値を出力する様に付け加える。
その出力を、 gdbなどのデバッガとscriptコマンドなどを用いてログを取り、 perlなどのスクリプトを用いて解析する。
実際に差分を確認したスクリプトの実行結果の一部を、 ソースコード\ref{cbc_origin_diff}に示す。

\lstinputlisting[frame=lrbt, label=cbc_origin_diff, caption=MoarVMとCbCMoarVMの実行命令の差分検知]{./codes/diff.txt}

左行がオリジナルのMoarVMの実行命令であり、 右行がCbCMoarVMの実行命令である。
出力している命令番号は、 それぞれLABELやCODESなどの命令リストの配列の番号と対応している為、 対応するCodeGear名を同時に出力している。
$\ast$が先頭に付随する行で差異が発生しており、 それぞれ実行している命令の番号が異なる事が確認出来る。
この例ではオリジナルのMoarVMは invoke\_o 命令を実行しているのに対し、 CbCMoarVMでは takeclosure 命令を実行している。

\section{CbCMoarVMの現在の実装}

CbCMoarVMは現在Perl6のサブセットであるNQP、 NQPで書かれたPerl6のビルドに成功している。
各言語のインタプリタであるnqp、 perl6共に、 CbCMoarVMの実行バイナリを利用して動作する。

デバッグ時の利便性などから、 現在はオリジナルのバイトコードインタプリタ部分を実行するか、 CbCで記述されたバイトコードインタプリタを実行するかをオプションを通して選択可能となっている。

またそれぞれのテストコードは、 移植元のMoarVMと同等のテスト通過率を示している。