\documentclass[twocolumn,twoside,9.5pt]{jarticle}
\usepackage[dvipdfmx]{graphicx}
\usepackage{picins}
\usepackage{fancyhdr}
\usepackage{abstract}
\usepackage{url}
%\pagestyle{fancy}
\lhead{\parpic{\includegraphics[height=1zw,keepaspectratio,bb=0 0 251 246]{pic/emblem-bitmap.pdf}}琉球大学主催 工学部情報工学科 卒業研究発表会}
\rhead{}
\cfoot{}

\setlength{\topmargin}{-1in \addtolength{\topmargin}{15mm}}
\setlength{\headheight}{0mm}
\setlength{\headsep}{5mm}
\setlength{\oddsidemargin}{-1in \addtolength{\oddsidemargin}{11mm}}
\setlength{\evensidemargin}{-1in \addtolength{\evensidemargin}{21mm}}
\setlength{\textwidth}{181mm}
\setlength{\textheight}{261mm}
\setlength{\footskip}{0mm}
\pagestyle{empty}

\usepackage{comment}
\usepackage{listings}
\lstset{
  language=C,
  tabsize=2,
  frame=single,
  basicstyle={\ttfamily\footnotesize}, %
  identifierstyle={\footnotesize}, %
  commentstyle={\footnotesize\itshape}, %
  keywordstyle={\footnotesize\bfseries}, %
  ndkeywordstyle={\footnotesize}, %
  stringstyle={\footnotesize\ttfamily},
  breaklines=true,
  captionpos=b,
  columns=[l]{fullflexible}, %
  xrightmargin=0zw, %
  xleftmargin=1zw, %
  aboveskip=1zw,
  numberstyle={\scriptsize}, %
  stepnumber=1,
  numbersep=0.5zw, %
  lineskip=-0.5ex,
}
\renewcommand{\lstlistingname}{ソースコード}
\usepackage{caption}
\captionsetup[lstlisting]{font={small, tt}}

\input{dummy.tex}
\renewcommand{\abstractname}{Abstract}
\begin{document}
\title{CbCによるPerl6処理系}
\author{135730B 氏名 {清水}{隆博} 指導教員 : 河野 真治}
\date{}
\twocolumn [
\maketitle
\begin{onecolabstract}
In Rakudo Perl6 itself written in a subset of Perl6 called NQP (NotQuitPerl).
NQP Bytecode is interpreted by MoarVM wrriten in C language.

We are developing Programing Language that name Continuation based C (CbC).
CbC has Code Gear and Data Gear as programing language units.
A transfer from a Code Gear to another Code Gear is performed using a CbC's goto statement,
which is compiled as a jump instruction in CbC.
MoarVM is going to implemented in C language, it can be rewritten in CbC.
In this thesis, consider rewriting the instruction dispatch part of MoarVM with CbC.

We successfully writtern MoarVM in CbC.
When an instruction executed by CbC enters the CPU cache, it runs faster than the original MoarVM.
\end{onecolabstract}]
\thispagestyle{fancy}


\section{Perl6のVMのモジュール化}
現在開発が進んでいるプログラミング言語にPerl6がある。
Perl6は、 入力されたソースコードを複数の仮想機械で実行可能なバイトコードにコンパイルする。
コンパイルされたバイトコードは、 Perl6専用のVMであるMoarVMやJavaVMが評価する。
MoarVMで動作する主流なPerl6の実装に、Rakudoがある。

RakudoそのものはPerl6のサブセットであるNQPで実装されている。
RakudoやNQPが動作するMoarVMはC言語で実装されている。
バイトコードから仮想機械を動作させる際、 バイトコード中のバイト列から、 実行する命令の処理を取得する必要がある。
この部分の実装が巨大なcase文やラベルgotoが使用されており、 モジュール化が行われていない。
モジュール化を行うことで、 それぞれに対して最適化を行うことが可能となる。
このモジュール化では、 Cの関数より小さな単位であるCbCが適していると考えられる。
その為、 本研究では、 MoarVMの命令対応部分のモジュール化の検討を行う。

%今後この部分を改善し、 速度向上をめに、 命令そのものを巨大なcase文から分離し、 モジュール化するのが望ましい。

\section{CbC}
Perl6処理系の改良には、 gccとLLVM/Clang上に実装した、 Continuation based C(CbC)を用いる。
CbCは関数よりも細かな単位である、 CodeGearを基本的な処理単位とし、 CodeGearの遷移でプログラムを記述するCの下位言語である。
CodeGearの宣言は、 \_\_codeという型を持つ関数として宣言する。
\_\_codeは内部的にはvoid型として扱っているが、 プログラマからの扱いはCodeGearである事を示す指示子のような役割である。
CodeGearはCの関数とは異なり返り値を持たず、 呼び差し元の関数に戻る代わりに別のCodeGearへ遷移する。
CbCにおけるCodeGear間の継続は、 スタックに値を積まず、 環境も遷移時に持たない為軽量継続と呼ぶ。
CbCは軽量継続を中心にプログラミングする事が可能であるため、 レジスタの移動などが行われない。
その為並列化やループ制御、 関数呼び出しにおけるスタック制御などを意識した、 プログラミングスタイルでプログラミングする事が可能である。
\lstinputlisting[label=cbcexample,  caption=cbc\_example.cbc]{src/cbc_example_test.cbc}

%\section{NQP}
%NQPとはPerl6のサブセットである．
%その為基本的な文法などはPerl6に準拠しているが，変数を束縛で宣言するなどの違いが見られる．
%
%NQPは最終的にはNQP自身でブートストラップする言語であるが,ビルドの最初にはすでに書かれたMoarvMByteCodeを必要とする．
%このMoarVMByteCodeの状態をStage0と言う．
%Perl6の一部はNQPを拡張したもので書かれている為,Rakudoを動作させる為にはMoarVMなどのVM,VMに対応させる様にビルドしたNQPがそれぞれ必要となる．
%NQPは与えられたStage0を使いStage1をビルドし，そのStage1を利用しStage2をビルドする事で生成できる．
%

\section{MoarVM}
MoarVMはPerl6の専用の処理系であり、 C言語で実装されている。
MoarVMはPerl6及び、Perl6の実装に用いられている、Perl6のサブセット言語であるNQPが生成したバイトコードを解釈する。
バイトコードは、 NQPのインタプリタから出力可能である。

JITコンパイルなどが現在導入されているが、 起動時間などが低速である問題がある。

MoarVMはレジスタマシンであり、 レジスタ操作や数値の加算を行う命令が存在する。
この命令は、 Perl6プログラムが変換されたバイトコードによって指定される。


\section{MoarVMのディスパッチ}
MoarVMはNQPから変換されたバイトコードを読み取り、 都度実行する。
MoarVMの場合この処理はMVM\_interp\_runという関数で行われている。
この関数内ではMoarVMが実行すべき命令が並んだ命令列を持ち、 その値で巨大なcase文、 またはCのラベルジャンプによって分岐させる。
分岐後は命令に応じた処理をMoarVMが行い、 次の命令を実行する。
分岐後は命令にごとの処理を実行し、 現在の命令列から、 実行した命令の長さ分命令列を進める。
進めた後にcase文の先頭もしくはCのラベルジャンプを利用して次の処理に遷移する。
この一連の処理を命令コードのディスパッチと呼ぶ。
命令コードの実行の中では、 現在のMoarVMのレジスタであるreg\_baseやスレッドごとの環境である構造体tcなどを参照する。
この方法の問題点として、 巨大なcase文に変換されてしまう事から、 命令に対応する処理のモジュール化が出来ない。
ラベルにbreak pointを設定できない為に、 デバッグし辛いなどが挙げられる。
\lstinputlisting[label=origdis,  caption=MoarVM内のインタプリタのディスパッチ]{src/dispatch.c}

\section{CbCMoarVMのディスパッチ}
本研究ではMoarVMは2018.04.01のバージョンで実装している。
命令コードの実行すべき単位は、 CbCのCodeGearの単位として扱える為、 命令処理をCodeGearに変換する。
変換されたCodeGearは、 オリジナルのMoarVMの命令コードと対応させる為に、 CodeGearの配列に格納する。
MoarVMはこの配列を参照し、 要素として得られるCodeGearに軽量継続を行う。
CodeGearでの処理が終了すると、 次のCodeGearを決定する為に必要な計算をcbc\_nextというCodeGearで行い，次の命令列に軽量継続する。
\lstinputlisting[label=codeseg,  caption=CbCMoarVM内のインタプリタの状態遷移]{src/cbc_codesegs.cbc}

\begin{figure}[ht]
     \begin{center}
     \includegraphics[width=50mm]{pic/cbc_next.pdf}
     \end{center}
     \caption{CbCにおけるMoarVMバイトコードインタプリタ内の状態遷移}
    \label{fig:perl6cbcinter}
\end{figure}


オリジナルのMoarVMとは異なり、同一関数上で実行する訳では無い。
従って、 MVM\_interp\_runで定義している局所変数のレジスタreg\_baseなどにアクセスすることは通常では出来ない。
CodeGearの遷移において、 これら必要なインタプリタの情報を纏めた構造体INTERを宣言し、 このポインタであるINTERPを引数として入力する。
各CodeGearではこのINTERPを経由することでレジスタ情報などにアクセスする。

この方法の利点としてCodeGearは単なる関数として扱える為、元のソースコードの様に同一ファイル内に全ての処理を書く必要がない。
またラベルにはbreak pointを設定する事が出来なかったが、 CodeGearはデバッガからは関数として見る事ができるため通常のCの関数の様にbreak pointを設定する事が可能である。

\section{まとめ}
現在はMoarVMを利用しNQP, Perl6のビルドが達成出来た。
またテストコードも、 元のMoarVMと同様の達成率を得た。
処理速度は再帰呼び出しなどを行っている例題では、 オリジナルのMoarVMより低速であるが、単純ループなどの例題の場合、 命令がCPUのキャッシュに残る場合は1.5sec高速に動く事が測定された。

\section{今後の課題}
本研究では、 MoarVM の命令ディスパッチ部分がCodeGearの集合に変換可能である事を示した。
また、 MoarVMの命令ディスパッチ部分をCodeGearの集合に変換するスクリプトや、 CbCで動作するMoarVMを作成した。
今後は速度向上を目的とし、 ディスパッチ時に配列集合にアクセスせず、 直接次のCodeGearに遷移する Threaded CodeをCbCを用いての実装を検討する。
また、 スクリプトが、使用する変数代入や分岐までの単位である、 基本ブロックを判別し、 動的にCbCのコードを生成するsymbolic executionなどの実装を検討する。

\nocite{*}
\bibliographystyle{junsrt}
\bibliography{reference}
\end{document}