Mercurial > hg > Papers > 2019 > anatofuz-thesis
changeset 40:1a2ad6e083bb
add chapter4.tex
author | anatofuz <anatofuz@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Thu, 14 Feb 2019 17:28:50 +0900 (2019-02-14) |
parents | c68174548ae0 |
children | 5169e3bc40f9 |
files | paper/chapter4.tex |
diffstat | 1 files changed, 95 insertions(+), 0 deletions(-) [+] |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/paper/chapter4.tex Thu Feb 14 17:28:50 2019 +0900 @@ -0,0 +1,95 @@ +\chapter{MoarVMのバイトコード実行} +\section{スクリプト言語のバイトコード} +プログラミング言語処理系は一般的に、 コンパイラ又はインタプリタに、 対象のソースコードを入力として与える。 +処理系はソースコード中の各文字列を、 トークンと呼ばれる形式に変換する。 +トークンは処理系によってはオブジェクトそのものなどに変換される。 +このトークンに変換するフェーズを字句解析と呼ぶ。 +変換されたトークンが、 対象のプログラミング言語の文法などに沿っているかどうかの確認を行う。 +文法に沿っていた場合、 文法に応じてトークンを木構造に変換する。 +これを構文解析と呼ぶ。 +構文解析の後は、 素朴なインタプリタ言語と呼ばれる種類のプログラミング言語の場合、 これらを木構造の根から順次実行する。 + +直接構文木を実行する場合、 実装そのものは単純になるが、 処理時間などが非常にかかる。 +現在の主流なスクリプト言語は、 一旦変換した構文木をバイトコードと呼ばれるバイナリ形式に変換する。 +この場合、 入力されたソースコードをバイトコードに変換する実装と、 変換されたバイトコードを評価する仮想機械に処理系が分けられる。 +仮想機械はOSのエミュレータではなく、 プロセス仮想マシンと呼ばれるものである。 +バイトコードを直接出力できる形式のプログラミング言語にJava、 Javaの仮想機械にJVMが存在する。 +内部的に利用しており直接は出力されない言語に、C言語で実装された MRIと呼ばれるrubyの実装などがあり、 この仮想機械にYARVが存在する。 +バイトコードを経由することで、 コンパイルを担当する実装と、 評価を担当する仮想機械の実装に分類する事が可能となり、 それぞれに適した最適化処理が実装可能となる。 +また実行する際の速度もバイトコードを経由することで上昇する。 + + +RakudoではPerl6、 NQPがそれぞれ対象のVMのバイトコードを生成し、 そのバイトコードをVMが実行する。 +バイトコード生成までの処理をフロントエンドと呼び、 バイトコードから評価を行う処理をバックエンドと呼ぶ。 +これらはJavaの様にバイトコードを出力も可能であるが、 基本的にはrubyなどの様に内部的にのみバイトコードを利用する。 +主に利用されている仮想機械にMoarVMがあり、 本研究ではMoarVMのバイトコード評価部分について検討をする。 + +\section{オリジナルのMoarVMの処理} +CbCでMoarVMを書き換える際に、 いきなり全てを実装する事は難しい。 +スクリプト言語の処理系の中心は、 与えられたバイトコードから実際の処理を逐次実装する部分である。 +その部分をバイトコードインタプリタと呼ぶ。 +今回はMoarVMの書き換えを検討する為に、 まずMoarVMのバイトコードインタプリタ部分の書き換えを行う。 +書き換えを行うにあたり、 MoarVMのオリジナルの箇所の実装を確認する。 +今回対象とするMoarVMのバージョンは2018.04.01である。 + +MoarVMのバイトコードインタプリタはsrc/core/interp.c中の関数 MVM\_interp\_runで定義されている。 +この関数では、 バイトコードに埋め込まれている命令に応じた処理を実行する。 + +関数内では、 解釈するべきバイトコード列が格納されている変数 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は、 それぞれの命令に対応したラベルとなる。 +次の命令に移動する際は、 マクロNEXT\_OPを用いてcur\_opを次の命令に移動させ、 opの値を再設定する。 +このopが実行すべき命令の番号が格納されている。 +opを用いて、ソースコード\ref{labels_list}に示す配列LABELSから、 命令に対応するラベルを取得する。 +LABELSはマクロOPが変換したラベルのリストである。 +ソースコード\ref{origin_dispatch}の場合、no\_opはcur\_opが0を指し、 const\_i8は1を指し示す。 + + +\lstinputlisting[frame=lrbt, label=labels_list, caption=MoarVMの命令ラベルが設定されている配列]{./codes/src/oplabels.h} + +ラベルgotoが利用できない場合、 マクロDISPATCHはswitch文に、 OPはcase文にそれぞれ変換される。 +cur\_opは数値そのものである為、 この場合はラベル配列へのアクセスは行われない。 + + +またソースコード\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}