view Paper/anatofuz.tex @ 39:e216aa15e656

update cbc_next
author Takahiro SHIMIZU <anatofuz@cr.ie.u-ryukyu.ac.jp>
date Fri, 09 Nov 2018 13:15:45 +0900
parents 7d9b01a98b9a
children 2a21f7911f92
line wrap: on
line source

% withpage: ページ番号をつける (著者確認用)
% english: 英語原稿用フォーマット
\documentclass{ipsjprosym}
%\documentclass[withpage,english]{ipsjprosym}

\usepackage[dvipdfmx]{graphicx}
\usepackage{latexsym}
\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}{Code}
\usepackage{caption}
\captionsetup[lstlisting]{font={small,tt}}
\usepackage{url}
\begin{document}

% Title, Author %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\title{CbCを用いたPerl6処理系}

%\affiliate{IPSJ}{情報処理学会}
\affiliate{IERYUKYU}{琉球大学工学部情報工学科}

\author{清水 隆博}{Takahiro SHIMIZU}{IERYUKYU}[anatofuz@cr.ie.u-ryukyu.ac.jp]
\author{河野 真治}{Shinji KONO}{IERYUKYU}[kono@ie.u-ryukyu.ac.jp]

%概要
\begin{abstract}
スクリプト言語であるPerl5の後継言語としてPerl6が現在開発されている.
Perl6は設計と実装が区分されており様々な処理系が開発されている.現在主流なPerl6はRakudoと言われるプロジェクトである.
RakudoではPerl6自体をNQP(NotQuitPerl)と言われるPerl6のサブセットで記述し,NQPをVMが解釈するという処理流れになっている.
このVMは任意のVMが選択できるようになっており,現在はMoarVM,JavaVM,Javascriptが動作環境として選択可能である.
主に利用されているVMにCで書かれたMoarVMが存在する.
MoarVMはJITコンパイルなどをサポートしているが,全体的な起動時間及び処理速度がPerl5と比較し非常に低速である.
この問題を解決するためにContinuation based C (CbC)という言語を一部用いてMoarVMの書き換えを行う.
本論文ではCbCを用いたMoarVMの書き換えを検討し,得られた知見について述べる.


\end{abstract}

\begin{jkeyword}
プログラミング言語, コンパイラ, CbC, Perl6, MoarVM
\end{jkeyword}

\maketitle

% Body %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{研究目的}
現在も広く使われているスクリプト言語PerlことPerl5の後継言語としてPerl6が開発されている.
Perl6は設計と実装が区分されており,現在広く使われている実装はRakudoと呼ばれるプロジェクトである.
Rakudoの実装はPerl6コンパイラ開発者用のサブセットであるNQP(NotQuitPerl)で実装されているPerl6の事を指す.
現在RakudoはNQPを解釈できる実行環境として,C言語で実装されたMoarVM,JVM,Javascript上で動作する様に開発されている.
Rakudoとして主に使われている処理系はMoarVMであるが,MoarVMの処理時間がPerl5などの多くのスクリプト言語と比較し非常に低速である.
その為現在日本国内ではPerl6を実務として利用するケースは概ね存在しない.
Perl6の持つ言語機能や型システムは非常に柔軟かつ強力であるため実用的な処理速度に達すれば言語の利用件数が向上することが期待される.
この問題を解決するために現在当研究室で開発しているContinuation Based C(以下CbC)を用いて改良を行う.
CbCはCよりさらにきめ細やかな記述が可能であるためスクリプト言語などのプログラミング言語の記述と親和性が高い事が推測される.
本研究はCbCをスクリプト言語の実装に適応した場合,どのような利点やプログラミング上の問題点に遭遇するかCbCの応用としての側面でも行う.
本稿ではまずCbC,Perl6の特徴及び現在の実装について述べ,本研究で行ったCbCで書き換えたMoarVMについてデバッグ手法も含め解説する.
そして本研究で得られたCbCを言語処理系に適応した場合の利点と欠点について述べ,今後の展望について記載する.

\section{CbC}
\subsection{CbCの概要}
CbCは当研究室で開発しているプログラミング言語である.
Cレベルでのプログラミングを行う場合,本来プログラマが行いたい処理の他にmallocなどを利用したメモリのアロケートやエラーハンドリングなどを記述する必要がある.
これらの処理をmeta computationと呼ぶ.これらmeta computationと通常の処理を分離することでバグの原因がmeta computation側にあるか処理側にあるかの分離などが可能となる.
しかしC言語などを用いたプログラミングでmeta computationの分離を行おうとすると,それぞれ事細かに関数やクラスを分割せねばならず容易ではない.
CbCでは関数よりmeta computationを細かく記述する為にCodeSegmentという単位を導入した.
またCodeSegmentの実行に必要なデータをDataSegmentという単位で受け渡す.
CbCではCodeSegment,DetaSegmentを基本単位として記述するプログラミングスタイルを取る.

\subsection{CodeSegmentとDataSegment}
CbCではCの関数の代わりにCodeSegmentを導入する.
CodeSegmentはCの関数宣言の型名の代わりに\_\_codeと書くことで 宣言できる.
\_\_codeはCbCコンパイラの扱いはvoidと同じ型であるが,CbCプログラミングではCodeSegmentである事を示す識別子としての意味で利用する.
CodeSegment間の移動はgoto文によって記述する.
\lstinputlisting[label=cbcexample, caption=cbc\_example.cbc]{./src/cbc_example.cbc}
Code\ref{cbcexample}に示すCbCのコードではmain関数からcs1,cs2に遷移し,最終的にdataの値が2となる.
CodeSegment間の入出力の受け渡しは引数を利用する.この引数は小さなDataSegmentであると言える.

\subsection{軽量継続}
%TBD
CbCでは次のCodeSegmentに移行する際,Cのgoto文を利用する.
通常のCの関数呼び出しの場合,スタックポインタを操作しローカル変数などをスタックに保存する.
CbCの場合スタックフレームを操作せず,レジスタの値を変更せずそのまま次のCodeSegmentに遷移する事が可能である.
通常Sechemeのcall/ccなどの継続は現在の位置までの情報を環境として所持した状態で遷移する.
対してCbCは環境を持たず遷移する為,通常の継続と比較して軽量であることから軽量継続であると言える.
CbCは軽量継続を利用するためレジスタレベルでのきめ細やかな実装が可能となっている.

\subsection{現在の実装}
CbCは現在主要なCコンパイラであるgcc及びllvmをバックエンドとしたclang上の2種類の実装が存在する.
gccはバージョン9.0.0に,clangは7.0.0に対応している.

\subsection{CbCコンパイラのバグ}
% 局所変数のポインタを握ったままgotoするとtail callにならない
CbCコンパイラは現在も開発中であり幾つかのバグが発見されている.
まずCodeSegment内で宣言した局所変数のポインタを別の変数などで確保した状態でgotoしてしまうとtail call最適化が切られる.
これはただの関数呼び出しになってしまう為,直接的な被害はないもののCbCとしての利点が損なわれてしまう.
また本来は操作しないはずのスタック領域の操作が入ってしまうため,プログラマの意図と反したスタックポインタなのど操作が行われてしまいバグが発生する可能性が存在する.

\subsection{CbCとCの互換性}
CbCコンパイラは内部的に与えられているソースコードがCbCであるかどうかを判断する.
この際にCodeSegmentを利用していない場合は通常のCプログラムとして動作する.
その為今回検証するMoarVMのビルドにおいてもCbCで書き換えたソースコードがあるMoarVMと,手を加えていないオリジナルのMoarVMの2種類を同一のCbCコンパイラでビルドする事が可能である.

またCからCbCへの遷移時に,再びCの関数に戻るように実装したい場合がある.
その際は環境付きgotoと呼ばれる手法を取る.これは\_CbC\_return及び\_CbC\_environmentという変数を渡す.
この変数は\_CbC\_returnが元の環境に戻る際に利用するCodeSegmentを指し,\_CbC\_environmentは復帰時に戻す元の環境である.
復帰する場合,呼び出した位置には帰らず,呼び出した関数の終了する位置に帰る.
\lstinputlisting[label=cbcreturn, caption=環境付き継続の例]{./src/return.cbc}
Code\ref{cbcreturn}に示す例ではc\_funcから環境付き継続でがcsに継続している.
通常c\_funcの返り値は-1であるが,csから環境付き継続でmainに帰る為にcsから渡される1がtestの値となる.


\subsection{言語処理系におけるCbCの応用}
CbCを言語処理系,特にスクリプト言語に応用すると幾つかの箇所に置いて利点があると推測される.
CbCにおけるCSはコンパイラの基本ブロックに相当する.
その為従来のスクリプト言語では主にcase文で記述していた命令コードディスパッチの箇所をCodeSegmentの遷移として記述する事が可能である.
CbCは状態を単位として記述が可能であるため,命令コードなどにおける状態を利用するスクリプト言語の実装は応用例として適していると考えられる.

\section{Perl6の概要}
この章では現在までのPerl6の遍歴及びPerl6の言語的な特徴について記載する.
\subsection{Perl6の構想と初期の処理系}
Perl6は2002年にLarryWallがPerlを置き換える言語として設計を開始した.
Perl5の言語的な問題点であるオブジェクト指向機能の強力なサポートなどを取り入れた言語として設計された.
Perl5は設計と実装が同一であり,Larryらによって書かれたC実装のみだった.Perl6は設計と実装が分離しており様々な処理系が開発されきた.
まず2005年に唐鳳によってHaskellで実装されたPugs\cite{pugs}が登場した.
Pugsは最初に登場したPerl6実装であり,この実装を基にしてPerl6の仕様も修正された.
現在Pugsは歴史的な実装となっており,更新はされていない.

\subsection{Parrot}
その後Pythonとの共同動作環境としてParrot\cite{parrot}が実装された.
ParrotはPASMと呼ばれるバイトコードを解釈可能なレジスタマシンである.
ParrotでのPerl6の実装はNQP(NotQuitPerl)と呼ばれるPerl6のサブセットでPerl6を記述するというアイディアの基実装された.
ParrotVMは2006年のversion8.1.0が最後のリリースである.
こちらもPugsと同様に現在のPerl6プロジェクトでは歴史的な実装とされている.
現在主に使用されている実装であるRakudoは2010年にRakudo-Starという一連のツール郡としてリリースされた.

Perl6は言語仕様及び処理実装がPerl5と大幅に異なっており,言語的な互換性が存在しない.
従って現在ではPerl6とPerl5は別言語としての開発方針になっている.
Perl6は現在有力な処理系であるRakudoから名前を取りRakuという別名がつけられている.

\subsection{Rakudo}

RakudoとはParrotで構想に上がったNQP,NQPに基づくPerl6を基にしたプロジェクトである.
RakudoがPerl6のコンパイラかつインタプリタであると考えても良い.
Rakudoは図\ref{fig:perl6construction}に示す構成になっている.
Rakudoにおけるコンパイラとは厳密には2種類存在する.
まず第1のものがPerl6,もしくはNQPをMoarVM,JVMのバイトコードに変換するNQPコンパイラである.
次にそのNQPが出力したバイトコードをネイティブコードに変換するVMの2種類である.
このVMは現在MoarVM,JavaVM,Javascriptを選択可能である.
Rakudo及びNQP projectではこのNQPコンパイラの部分をフロントエンド,VMの部分をバックエンド\cite{rani1}と呼称している.
NQPで主に書かれ,MoarVMなどNQPが動作する環境で動くPerl6のことをRakudoと呼ぶ.
Perl6はNQP以外にものNQPを拡張したPerl6自身で書かれている箇所が存在し,これはNQPコンパイラ側でMoarVMが解釈可能な形へ変換を行う.

\begin{figure}[ht]
     \begin{center}
     \includegraphics[width=70mm]{fig/perl6nqp.pdf}
     \end{center}
     \caption{Perl6の構成}
    \label{fig:perl6construction}
\end{figure}

\subsection{NQP}

RakudoにおけるNQP\cite{nqp}は現在MoarVM,JVM上で動作し,MoarVMを一部利用することでNodeJSからも動作させる事が可能である.
NQPはPerl6のサブセットであるため主な文法などはPerl6に準拠しているが幾つか異なる点が存在する.
NQPは最終的にはNQP自身でブートストラップする言語であるが,ビルドの最初にはすでに書かれたMoarvMByteCodeを必要とする.
このMoarVM~yteCodeの状態をStage0と言い,ディレクトリ名として設定されている.
Perl6の一部はNQPを拡張したもので書かれている為,Rakudoを動作させる為にはMoarVMなどのVM,VMに対応させる様にビルドしたNQPがそれぞれ必要となる.
現在のNQPではMoarVM,JVMに対応するStage0はそれぞれMoarVMBytecode,jarファイルが用意されており,Javascriptではバイトコードの代わりにランタイム独自のModuleLoaderなどが設計されている.
MoarVMのModuleLoaderはStage0あるMoarVMBytecodeで書かれた一連のファイルが該当する.


Stage0にあるファイルをmoarvmに与えることでnqpのインタプリタが実行される様になっている.
これはStage0の一連のファイルはmoarvm bytecodeなどで記述されたNQPコンパイラのモジュールである為である.
NQPは6modelと呼ばれるオブジェクトモデルを採用としているが,これを構築する為に必要なNQPCORE,正規表現系のQRegex,MoarVMのModuleLoaderなどがMoarVMBytecodeで記述されている.これらMoarVMBytecodeの拡張子は.moarvmである.
MoarVMに対してStage0のディレクトリにライブラリパスを設定し,nqp.moarvmを実行させることでnqpの対話型環境が起動する.

\begin{figure}[ht]
     \begin{center}
     \includegraphics[width=70mm]{fig/stagenqp.pdf}
     \end{center}
     \caption{NQPのビルドフロー}
    \label{fig:nqpbuild}
\end{figure}

NQPのビルドフローを図\ref{fig:nqpbuild}に示す.
実際にperl6を動かすためにはself buildしたNQPコンパイラが必要となる.その為にstage0を利用してStage1をビルドしNQPコンパイラを作成する.
Stage1は中間的な出力であり,生成されたNQPファイルはStage2と同一であるが,MoarVMBytecodeが異なる.
Perl6では完全なセルフコンパイルを実行したNQPが要求される為,Stage1を利用してもう一度ビルドを行いStage2を作成する.

Perl6のテストスイートである「Roast\cite{roast}」やドキュメントなどによって設計が定まっているPerl6とは異なりNQP自身の設計は今後も変更になる可能性が開発者から公表されている.
現在の公表されているNQPのオペコードはNQPのリポジトリ\cite{nqpopcode}に記述されているものである.


\subsection{Rakudo Perl6}
Rakudo実装上におけるPerl6はRakudo Perl6と呼ばれているGitリポジトリで管理されているプログラムのことである.
前述した通りRakudo Perl6はPerl6のサブセットであるNQPを用いて記述されている.
従ってyaccやlexと言ったPerl5の文字解析,構文解析に利用していたプログラムは利用せず,NQP側で構文定義などを行っている.
NQPはNQP自身でBootstrappingされている為,Rakudo Perl6のbuild時にはNQPの実行環境として要したVM,それに基づいてbuildしたNQPがそれぞれ必要となる.

言語的な特徴としては独自にPerl6の文法を拡張可能なGrammer,Perl5と比較した場合のオブジェクト指向言語としての進化も見られる.
またPerl6は漸進的型付け言語である.
従来のPerlの様に変数に代入する対象の型や文脈に応じて型を変更する動的型言語としての側面を持ちつつ独自に定義した型を始めとする様々な型に静的に変数の型を設定する事が可能である.


\subsection{現在のPerl6}
Perl6の言語仕様\cite{perl6design}とその時点での実装状況を纏めた公式ドキュメント\cite{perl6doc}は分離している.
従来は言語仕様は自然言語の仕様書であったが,現在はテストスイートである「Roast\cite{roast}」そのものと定義されている.
現在のPerl6の仕様を読む場合Roastを確認し,現在rakudo上に実装されている機能を見る場合は公式ドキュメントを確認する必要がある.


\section{CbCによるMoarVM}
この章では改良を行ったPerl6処理系であるMoarVMについて述べる.
\subsection{方針}
MoarVMそのものをCbCで書き換えることも考えられるがMoarVM自体既に巨大なプロジェクトである為すべてを書き換える事は困難である.
その為まず比較的CbCで書き換えることが容易な箇所を修正する.
前章までに述べた通りCbCのCodeSegmentはコンパイラの基本ブロックに該当する.
従ってMoarVMにおける基本ブロックの箇所をCodeSegmentに書き換える事が可能である.
MoarVMにおける基本ブロックはインタプリタが実行するバイトコードごとの処理に該当する.

\subsection{MoarByteCodeのディスパッチ}
MoarVMのバイトコードインタプリタはsrc/core/interp.cで定義されている.
この中の関数MVM\_interp\_runで命令に応じた処理を実行する.
関数内では命令列が保存されているcur\_op,現在と次の命令を指し示すop,Threadの環境が保存されているThreadcontextなどの変数を利用する.
命令実行は大きく二種類の動作があり,Code\ref{orig_macro}に示すCのgotoが利用できる場合はMVM\_CGOTOフラグが立ちラベル遷移を利用する.
それ以外の場合は巨大なcase文として命令を実行する.

ラベル遷移を利用する場合はラベルテーブルにアクセスし,テーブルに登録されているアドレスを取得し,マクロNEXTで遷移する.
Code\ref{cbc_dispatch_c}に示すno\_opは何もせず次の命令に移動する為,NEXTのみ記述されている.

このラベルテーブルの中身はラベルが変換されたアドレスであるため,実際に呼ばれている命令コードの名前はデバッガレベルでは確認できない.
Cレベルでのデバッグ時にはアドレスと実際に呼ばれる箇所を確認する事に手間がかかる.
巨大なcase文として実行された場合,実行時間が遅いだけでなく,ラベル遷移と共存させて記述を行っている為Cのソースコードにおける可読性も低下する.


\lstinputlisting[label=orig_macro, caption=interp.cのマクロ部分]{./src/orig_macro.c}

\lstinputlisting[label=dispatch_c, caption=オリジナル版MoarVMのバイトコードディスパッチ]{./src/dispatch.c}

interp.cでは命令コードのディスパッチはマクロを利用したcur\_opの計算及びラベルの遷移,もしくはマクロDISPATCHが展開するswitch文で行われていた.
CbCMoarVMではこの問題を解決するために,それぞれの命令に対応するCodeSegmentを作成し,CodeSegment名前を要素として持つCbCのCodeSegmentのテーブルを作成した.
このCodeSegmentのテーブルを参照するCodeSegmentはcbc\_nextであり,この中のマクロNEXTはinterp.cのマクロNEXTをCbC用に書き直したものである.

\lstinputlisting[label=cbc_dispatch_c, caption=CbCMoarVMのバイトコードディスパッチ]{./src/cbc-interp-next.cbc}

\subsection{命令実行箇所のCodeSegmentへの変換}
ラベルテーブルやcase文のswitch相当の命令実行箇所をCbCに変換し,CodeSegmentの遷移として利用する.
interp.cはCode\ref{dispatch_c}に示すスタイルで記述されている.



OP(.*)の.*に該当する箇所はバイトコードの名前である.通常このブロックにはLABELから遷移する為,バイトコードの名前はLABELSの配列の添字に変換されている.
そのため対象となるCodeSegmentをLABLESの並びと対応させ,CodeSegmentの配列CODESとして設定すればCodeSegmentの名前は問わない.
今回はCodeSegmentである事を示す為にsuffixとしてcbc\_をつける.


命令の実行処理でMoarVMのレジスタであるreg\_baseや命令列cur\_opなどの情報を利用しているが,これらはMVM\_interp\_run内のローカル変数として利用している.
ラベルを利用しているオリジナル版では同一関数内であるためアクセス可能であるが,CodeSegment間の移動で命令を表現するCbCではアクセスできない.
その為インタプリタの情報を集約した構造体interを定義し,この構造体へのポインタであるINTERP型の変数iをCodeSegmentの入出力として与える.
CodeSegment内ではINTERPを経由することでインタプリタの各種情報にアクセスする.
CodeSegment間の遷移ではレジスタの値の調整は行われない為,入力引数を使ってレジスタマッピングを管理できる.
その為INTERPのメンバであるMoarVMのレジスタそのものをアーキテクチャのレジスタ上に乗せる事が可能である.

命令実行中のCodeSegmentの遷移を図\ref{fig:perl6cbcinter}に示す.
この中で実線で書かれている部分はCbCのgoto文で遷移し,波線の箇所は通常のCの関数呼び出しとなっている.

現在のCbCMoarVMは次の命令セットのディスパッチをcbc\_nextが行っていた.
その為cbc\_nextから命令コードに対応するCodeSegmentに継続し,CodeSegmentからcbc\_nextに継続するサイクルが基本の流れである.
CodeSegment内からCの関数は問題なく呼ぶ事が可能であるため,Cの関数を利用する処理は変更せず記述する事ができる.
また変換対象はswitch文であるため,breakせず下に落ちた場合に対応するように別のCodeSegmentに継続し,その後cbc\_nextに継続するパターンも存在する.

\lstinputlisting[label=cbc_codesegs_c, caption=CbCMoarVMのバイトコードに対応するCodeSegment]{./src/cbc_codesegs.cbc}

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

バイトコードの数は膨大である為,すべてを手作業で変換する事は望ましくない.
本研究ではPerlScriptを用いてinterp.cからCbCのCodeSegmentを自動生成するスクリプトを作成した.
このスクリプトでは以下の修正手続きを実行する.

\begin{itemize}
  \item OP(.*)の.*部分をCodeSegmentの名前として,先頭にcbc\_をつけた上で設定する.
  \item cur\_opなど構造体INTERのメンバ変数はポインタiから参照するように修正する
  \item GC対策のためマクロMVMROOTを使い局所変数のポインタをスタックに積む箇所は,局所変数をstatic化する
  \item 末尾のgoto NEXTをgoto cbc\_next(i)に修正する
  \item case文で下のcase文に落ちている箇所は,case文に対応するCodeSegmentに遷移する様にgoto文を付け加える
\end{itemize}


上記Code\ref{cbc_codesegs_c}ではcbc\_const\_i8などがcase文の下のcase部分に該当するcbc\_const\_i64に遷移する様に変換されている.
またcbc\_pushcompscではMVMROOTに局所変数scを渡している為,これをstaticで宣言し直している.

現在CbCで記述されたOSであるGearsOSにはInterfaceが導入されている.
これはJavaのinterface,Haskellの型クラスに該当する概念であり,次のCodeSegmentにInterface経由で継続する事が可能である.
Interfaceは現在のMoarVMには実装されていない為,今後ThreadeCodeの実装を行うにあたり導入を検討している.

\subsection{Threaded Code}
現在のMoarVMは次の命令をバイトコードからディスパッチし決定後,ラベルジャンプを利用し実行している.
この処理ではディスパッチの箇所にコストが掛かってしまう.
CbCをMoarVMに導入することで,バイトコード列を直接サブルーチンコールの列に置き換えてしまう事が可能である.
これはCbCが基本ブロックの単位と対応している為である.
CbCでは現在ディスパッチを行うCodeSegmentであるcbc\_nextを利用しているが,Threaded Codeを実装するにあたり,
cbc\_nextと次のCodeSegmentに直接遷移するcbc\_fixt\_nextの実装を予定している.

また段階的に現在8バイト列を1命令コードとして使用しているが,これを16バイトなどに拡張し2命令を同時に扱えるように実装する事なども検討している.

%CbCはCodeSegmentで末尾最適化(Tail call optimization)を行う.
%これはCodeSegmentは必ず関数呼び出しではなくgotoで次の状態に遷移する為にスタック領域の操作が必要とならない為である.
%現在のCbCコンパイラの実装ではCodeSegmentからCの関数に戻る場合は末尾最適化を切り,CodeSegment間の遷移では末尾最適化が行われる.
%末尾最適化を応用することでContinuation-passingスタイルのThreaded Codeの実装が可能となる.\cite{threadedcode}
%またCodeSegment自体を直接次の遷移先として設定することも可能であるため,CbCならThrededCodeを実装するアプローチが複数検討出来る.

%現在のCbCMoarVMは次の命令セットのディスパッチをcbc\_nextというCodeSegmentで処理している.
%これは元のMoarVMの命令ディスパッチで行われる現在のオペコードを示すcur\_opと命令列opの操作及び次のラベルに遷移するマクロに該当する.
%CbCMoarVMではラベルに対しての遷移の代わりにMoarVMの命令のCodeSegmentの集合体である配列CODESにアクセスし,その要素であるCodeSegmentに対して遷移する形を取っている.
%この一連の処理がオーバーヘッドになる為,今後はcbc\_fixt\_nextというCodeSegmentを導入し直接次の命令に該当するCodeSegmentへgotoする様に実装する予定である.

\subsubsection{perlcc}
Perl5においてはperlccというモジュールが開発されている.
これはPerl5内部で利用しているPerlバイトコードを,PerlのC APIであるXS言語の様なCのソースファイルに埋め込み,それをCコンパイルでコンパイルするというものである.
perlccを利用することでPerlインタプリタが無い状況でも可動するバイナリファイルを作成する事が可能である.
しかしPerlccはPerlスクリプトが複雑になるほど正確にCに移植を行う事が出来ず,現在ではPerlのコアモジュールから外されている.
PerlccはPerlのバイトコードをCへの変換のみ行う為,Cで実装されているPerl経由で実行した場合と処理速度はほぼ変わらない.
またPerlccで生成されたCのソースコードは難解であり,これをデバッグするのが困難でもある.
MoarVMでthreaded codeを実現出来た場合,その箇所のみCbCプログラムとして切り出す事が可能である為perlccと似たツールを作成することも可能である.
この場合,Perl6を通常動かした際とは異なりバイトコードインタプリタに到達する前の処理が無くなる為多少の高速化が望めると推測できる.

\subsection{Cのインライン展開}
CbCのCodeSegmentはgoto文で遷移するため,次のCodeSegmentが一意に決定している場合Cコンパイラ側でインライン展開する事が可能である.
CodeSegmentがインライン展開される限界については別途研究する必要があるが,CbCを利用した場合その箇所でもコストを低く設計する事が可能である.

\section{MoarVMのデバッグ}

MoarVM自体のデバッグはMoarVMのリポジトリにテストコードが付随していない為単体では実行不可能である.
本研究ではMoarVMのデバッグにおけるCデバッガの使用方法とMoarVMのテスト方法についても考案する.
 
\subsection{MoarVMのBytecodeのデバッグ}
moarに対してmoarvm bytecodeをdumpオプションを付けて読み込ませるとmoarvmのbytecodeがアセンブラの様に出力される.
しかしこれはmoarvmが実行したbytecodeのトレースではなくmoarvm bytecodeを変換したものに過ぎない.
また,明らかに異なる挙動を示す両者のmoarを利用しても同じ結果が返ってきてしまう.
そのため今回のMoarVMBytecodeインタプリタの実装のデバッグにはこの方法は適さない.
従って実際に実行した命令を確認するにはgdbなどのCデバッガを利用してMoarVMを直接トレースする必要がある.

CbC側はCode\ref{cbc_b}に示す様にcbc\_nextにbreak pointを設定する.
オリジナル側は次のオペコードの設定のマクロにダミーの関数を呼び出すように修正し,そこにbreak pointを設定する.
CbC側ではCodeSegmentの名前をデバッガ上で直接確認できるが,オリジナル版はLABLEの配列の添え字から自分でどのオペコードに対応しているかをデバッガの外で探す必要がある.

添字を確認するためにはCode\ref{orig_b}に示すようにオリジナルのMoarVMの場合cur\_opの値をMVMuint16のポインタでキャストし,これが指す値を出力する.
break pointを掛けているダミー関数ではcur\_opにアクセスする事が出来ない為,スタックフレームを一つupする必要がある.
\lstinputlisting[label=cbc_b, caption=CbCMoarVMに対してのbreak point設定]{./src/cbc_breakpoint.txt}
\lstinputlisting[label=orig_b, caption=オリジナル版MoarVMに対してのbreak point設定]{./src/origin_b_set.txt}


\subsection{MoarVMの並列デバッグ手法}
しかしMoarVMが実行する命令は膨大な数がある.
その為gdbでMoarVMをCbCとオリジナル版での並列デバッグを人間が同時に行うことは困難である.
Perlなどのスクリプトを用いて自動的に解析したいため,ログを残す為にscriptコマンドを実行した状態でgdbを起動する.


\lstinputlisting[label=debug_origmoar, caption=オリジナル版MoarVMのバイトコードのトレース]{./src/origin_breakpoint.txt}

CbCとオリジナルのCODES,LABELの添字は対応している為,ログの解析を行う際はそれぞれの添字を抽出し違いが発生している箇所を探索する.
これらはscriptコマンドが作成したログを元に異なる箇所を発見するスクリプトを用意し自動化する.
\lstinputlisting[label=logs2, caption=バイトコードの差分検知の一部分]{./src/logs2.txt}

違いが生じている箇所が発見できた場合,その前後のCodeSegment及びディスパッチ部分にbreak pointをかけ,それぞれの変数の挙動を比較する.
主にcbc\_return系の命令が実行されている場合は,その直前で命令を切り替えるcbc\_invoke系統の命令が呼ばれているが,この周辺で何かしらの違いが発生している可能性が高い.
また主に次のCodeSegmentに遷移する際にCbCコンパイラのバグが生じている可能性もある為,アセンブラレベルの命令を確認しながらデバッグを進めることとなる.



\subsection{CbCコンパイラによるバグ}
現在までのCbCは複数個の入出力をCodeSegmentに与えるユースケースで利用していた.
CbCコンパイラ自身はそれぞれ用意したテストスイートを通化するものの,MoarVMの様な巨大なプロジェクトのCSをコンパイルを実行する場合,予期せぬバグが発生した.
主にCS間のgotoにおけるtail callフラグの除去や,DSとして渡している構造体の変数のアドレスがスタックポインタの値より上位に来てしまい,通常のCの関数をcallした際にローカル変数の領域がDSのアドレスの周辺を利用してしまう.
その為DSの構造体の値が書き換わり,CからDSにreturnした際にDSの構造体が破壊されるバグである.
このバグは先程の並列デバッグを行いながらプログラムカウンタや変数の動きをトレースする事などで発見することが出来る.
現状ではCbCコンパイラがプログラマの意図と反する挙動を取るためCbCコンパイラのバグを回避するプログラミングが要求されている.
本来コンパイラ側のバグを回避するプログラミングをプログラマに要求する事は好ましくない.
従ってCbCコンパイラ自身の信頼性を向上させる事も今後の課題となっている.

また現在はclang上に実装したCbCコンパイラではCodeSegment内部のtaill call除去のエラーが発生してしまう為コンパイルする事が出来ない.
その為現在はgcc上に実装したcbcコンパイラを利用しgdbを利用しデバッグを行う.


\section{CbCを用いる事についての利点と欠点}
MoarVMの様な巨大なスクリプト言語処理系にCbCを適応した所現在までに複数の利点と欠点が発見された.
本章ではまず利点を述べ,次に現段階でのCbCを適応した場合の欠点について考察する.

\subsection{利点}
\subsection{コード分割}
オリジナルのMoarVMでは命令コードに対応する箇所はラベルジャンプ,もしくはswitch文で実装されていた.
その為同じCファイルに命令コードの実行の定義が存在しなければならない.
今後MoarVMに新たなバイトコードが導入されていく事を考えるとinterp.cが巨大になる可能性がある.
関数単位での処理の比重が偏る事に加え,
switch文中に書かれている処理は他の関数から呼ぶ事が出来ないため,余計な手間がかかる箇所が発生すると考えられる.

CbCMoarVMの場合,CodeSegmentとして基本ブロックを記述出来る為オリジナルのMoarVMの様にswtich文のブロック中に書く必要性が無くなる.
その為類似する命令系をコード分割し,モジュール化する事が可能である.
またCbCはgoto文で遷移する以外は通常のCの関数と同じ扱いをする事が可能である.
従ってCodeSegment内部の処理を別の箇所から使用する事も可能となる為再利用性も向上する.

\subsection{ThreadeCode}
ThrededCodeを実装する場合,通常命令ディスパッチの箇所と,実際に実行される命令処理を大幅に変更しなければならない.
CbCを用いた実装の場合,命令処理はただのCodeSegmentの集合である.
その為CodeSegmentをThrededCodeに対応した並びとして選択する事ができれば命令処理部分の修正をほぼせずにThrededCodeを実現する事が可能である.

またCodeSegmentはバイトコードレベルと同じ扱いができるため,ThrededCodeそのものを分離して最適化をかける事が可能である.
これもCodeSegmentが関数単位として分離できる事からの利点である.


\subsubsection{MoarVMのデバッグ}
MoarVMのバイトコードインタプリタの箇所はオリジナルの実装ではラベルジャンプを用いて実装されている.
その為,直接ラベルにbreak pointをかける事が出来ない.
作業者がデバッガが読み込んでいるCソースコードの位置を把握し,行番号を指定してdebug pointを設定する必要があった.

CbCMoarVMの場合,CodeSegment単位でバイトコードの処理単位を記述している為,通常の関数と同じく直接CodeSegmentにデバッグポイントをかける事が可能である.
これはCプログラミングの関数に対してのデバッグで,状態ごとにbreak pointをかける事が出来ることを意味する.
通常のC言語で言語処理系を実装した場合と比較して扱いやすくなっていると言える.
さらにラベルテーブルでの管理場合,次のバイトコード箇所は数値でしか確認できず,実際にどこに飛ぶのかはラベルテーブル内と数値を作業者が手作業で確認する必要があった.
スクリプトなどを組めば効率化は出来るがデバッガ上で完結しない為手間がかかる.
CbC実装ではCODESテーブル内は次のCodeSegmentの名前が入っている為,数値からCodeSegmentの名前をデバッガ上で確認する事が出来る.

\subsection{JITコンパイルの応用}
現在MoarVMはLuaJit\cite{luajit}を搭載しJITコンパイルを行っている.
LuaJITそのものをCbCに適応させるわけではないが,CbCのABIにJITされたコードを合わせる事が可能であると推測できる.
% \subsection{単純なループ処理の測定}
% 簡単な例題としてfor文を用いて100000回ループさせ,ある変数をインクリメントするというプログラムを作成する.
% 今回の評価対象としてPerl6は2018年4月にリリースされたMoarVM,NQP,Rakudoの実装を用いる.
% Perl5は5.26.2を利用した.

% \begin{table}[htb]
% 	\begin{tabular}{|c|c|c|} \hline
% 	 ループ回数 & Perl5 (sec) & Perl6(sec) \\  \hline \hline	 
% 	 1000000 & 0.131 & 1.444 \\ \hline
% 	 10000000 & 0.131 & 1.444 \\ \hline
% 	 100000000 & 3.258 & 124.69 \\ \hline
% 	\end{tabular}
% \end{table}

\subsection{欠点}
本来処理系は広く使われる為に著名なOSSなどを利用して開発するのが良いが,CbCプロジェクトの認知度が低いという現状がある.

また,前章までに複数述べた通りCbCコンパイラが現在非常にバグを発生させやすい状態になっている.
CbCコンパイラはgccとllvm/clangに実装している為,これらのアップデートに追従する必要がある.
しかしコンパイラのバージョンに応じてCbCで利用するコンパイラ内のAPIが異なる場合が多く,APIの変更に伴う修正作業などを行う必要がある.

CbCMoarVMではCからCodeSegmentへ,CodeSegmentからCへの遷移などが複数回繰り返されているが,この処理中のCodeSegmentでのtail callの強制が非常に難関である.
tail callの強制には関数定義の箇所や引数,スタック領域のサイズ修正などを行う必要がある.
現在のバグではCodeSegment内部での不要なスタック操作命令を完全に排除しきれていない.

またCodeSegmentからCに帰る場合,環境付き継続を行う必要がある.
Cの関数の末尾でCodeSegmentを呼び出している場合など環境付き継続を使用しなくても良いケースは存在するが,頻繁にCとCbCを行き来する場合記述が冗長になる可能性はある.

\section{今後の課題}
本論文ではCbCによってPerl6の処理系であるMoarVMインタプリタの一部改良とその手法を示した.
CbCのCodeSegment部分を用いることできめ細やかな記述が出来,デバッグし辛い箇所もbreakpointの設定などが容易になった.

今後CbCでの開発をより深く行っていくにあたり,CbCコンパイラそのものの信頼性を向上させる必要がある.
MoarVMの開発を行うにあたり新たに発見された複数のバグを修正し,より安定するコンパイラにする為に改良を行う.

現在CbCMoarVMで直接バイトコードを入力した場合のnqpのテストは\%パスする.
また数値の計算と出力などの簡単なNQPの例題を作成し,オリジナルのNQP,moarvmでバイトコード化したものを入力した際も正常に動作している.
今後はさらに複雑な例題やPerl6の独自文法でも動くかどうかの実験を行う.

MoarVMではGCからオブジェクトを守る為にMVMROOTというマクロを利用し,局所変数のポインタをスタックに登録する処理を行っている.
GCの制御を効率的に行えば本来は必要ない処理であり,実行するとCodeSegmentの優位性が損なわれてしまう.
従ってMoarVMのGCの最適化を行う.

また高速化という面では,Perlの特徴である正規表現に着目し,正規表現の表現のみ高速で動く最適化の導入なども検討している.
他にrakudoのコンパイラ系統からCbCのコードを直接生成させ,それをllvmでコンパイルすることによってLLVMの最適化フェーズを得て
高速化することも可能であると推測できる.

Perl6の開発は非常に活発に行われている為,CbCMoarVMの最新版の追従も課題となっている.
現在はinterp.cからPerlスクリプトを用いて自動でCbCのCodeSegmentを生成している.
今後の開発領域の拡大と共により効率的にCbCコードへの自動変換も複数のCコードに対応する様に開発を行っていく.

%å\subsection{MoarVMの処理流れ}
%MoarVMはC言語で実装されており,Perl5で記述されたConfigure.plを


% BibTeX を使用する場合 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\nocite{*}
 \bibliographystyle{ipsjsort}
 \bibliography{reference}

\end{document}