title: CbCによるPerl6処理系
author: Takahiro Shimizu, Shinji Kono
profile: 琉球大学
lang: Japanese
code-engine: coderay


## 研究目的
-  スクリプト言語である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の書き換えを検討し,並列デバッグ方法などについて検討する.


## Continuation Based C (CbC)

- Continuation Based C (CbC) はCodeGearとDataGearを単位として用いたプログラミング言語である.
- CodeGearはCの通常の関数呼び出しとは異なり，スタックに値を積まず, 次のCodeGearにgoto文によって遷移する.
- このgoto文による遷移を軽量継続と呼ぶ．
- CbCは軽量継続を取り入れたCの下位言語であり, C言語のAPIを利用可能なCと互換性のある言語である．

## CodeGearとDetaGear

- Cの関数の代わりにCodeGearという単位をCbCでは導入している．
- CodeGearはCの関数宣言の型名の代わりに`__code`と書く事で宣言出来る．
- CodeGearの引数を遷移先のCodeGearと揃えることでレジスタに変数を確保した状態で軽量継続可能である．
- その為CodeGearの引数は入出力としての意味があり, DataGearと呼んでいる．

```
extern int printf(const char*,...);
  int main (){
     int data = 0;
     goto cg1(&data);
}
__code cg1(int *datap){
      (*datap)++;
    goto cg2(datap);
}
__code cg2(int *datap){
    (*datap)++;
    printf("%d\n",*datap);
}
```

## CbCの現在の実装

- CbCは現在2種類の実装がある．
  - gcc (version 9.0.0)
  - llvm/clang (version 7.0.0)

## 言語処理系の応用
- CbCではCodeGearを処理単位として利用でき, これはコンパイラの基本ブロックに相当する．
- 従来のスクリプト言語などの処理系では, 主にcase文で実装していた命令コードディスパッチの箇所をCodeGearの遷移として記述する事が可能である．
- CodeGearの遷移として記述する事で, 命令処理ごとに分割する事が可能となり, モジュール化が可能となる．
- CodeGearとCodeGearの遷移時に入出力のインターフェイスを揃える事で, レジスタに変数が割り振られたまま軽量継続が可能となり, レジスタレベルの最適化が可能となる．
- これらの検証とPerl6の高速化を行う為に, CbCを用いてPerl6処理系の書き換えを行っていく．

## Perl6の概要

- Perl6とはPerl5の後継言語として当初開発が開始された言語である．
- 仕様と実装が分離しており, 仕様は公式テストスイートであるRoastそのものとなっている．
- 歴史的にHaskellで実装されたPugs, Pythonとの共同基盤を目指したParrotなどの実装が存在する．
- 言語仕様としては漸進的型付け言語であり, 従来のPerl5とは互換性が無い．
- 現在の主要な実装はRakudoと呼ばれる実装である．

## Rakudo
- Rakudoとは現在のPerl6の主力な実装である．
- 実行環境のVM, Perl6のサブセットであるNQP(NotQuitPerl), NQPで記述されたPerl6(Rakudo)という構成になっている．
- VMはCで書かれたPerl6専用のVMであるMoarVM, JavaVMが選択可能である．
- 現在はMoarVMがRakudoの中でも主流なVM実装となっている．

## Rakudo
- Rakudoにおけるコンパイラは2種類存在する
    - Perl6やNQPのコードをVMのバイトコードに変換するコンパイラ
    - NQPが出力したVMのバイトコードをネイティブコードに変換するコンパイラ
- NQPの処理系nqp及び, Perl6のインタプリタである perl6は, それぞれセルフコンパイルしたものを利用する
- Perl6は純粋なNQPではなく, Perl6自身によって拡張され記述されている箇所も存在する

## MoarVM

- Perl6専用のVMであり, Cで記述されている
- レジスタマシンとして実装されている．
- MoarVMはバイトコードインタプリタを `src/core/interp.c` で定義しており, この中の関数 `MVM_interp_run` で命令に応じた処理を実行する

## MVM_interp_run

- MVM_interp_runでは次のオペコードをフェッチする際に `NEXT_OP` マクロを介して計算を行う．
- オペコードが対応する命令を実行する際は, `MVM_CGOTO` フラグが立っている場合はCのラベルgotoを利用し, 使えない場合はswitch文を利用して遷移する．


```
#define NEXT_OP (op = *(MVMuint16 *)(cur_op), cur_op += 2, op)

#if MVM_CGOTO
#define DISPATCH(op)
#define OP(name) OP_ ## name
#define NEXT *LABELS[NEXT_OP]
#else
#define DISPATCH(op) switch (op)
#define OP(name) case MVM_OP_ ## name
#define NEXT runloop
#endif
```

## MVM_interp_run

- ラベル遷移を利用する場合は配列`LABELS`にアクセスし, ラベル情報を取得する

```
static const void * const LABELS[] = {
    &&OP_no_op,
    &&OP_const_i8,
    &&OP_const_i16,
    &&OP_const_i32,
    &&OP_const_i64,
    &&OP_const_n32,
    &&OP_const_n64,
    &&OP_const_s,
    &&OP_set,
    &&OP_extend_u8,
    &&OP_extend_u16,
    &&OP_extend_u32,
    &&OP_extend_i8,
    &&OP_extend_i16,
```

## MVM_interp_run

- DISPATCHマクロは次の様に記述されており, この中の `OP` で宣言されたブロックがそれぞれオペコードに対応する処理となっている．
- この中では `GET_REG` などのマクロを用いてMoarVMのレジスタにアクセスする．
- `cur_op`は次のオペコードを意味し, マクロ `NEXT` で決められた方法で次のオペコードに遷移する．

```
DISPATCH(NEXT_OP) {
    OP(no_op):
        goto NEXT;
    OP(const_i8):
    OP(const_i16):
    OP(const_i32):
        MVM_exception_throw_adhoc(tc, "const_iX NYI");
    OP(const_i64):
        GET_REG(cur_op, 0).i64 = MVM_BC_get_I64(cur_op, 2);
        cur_op += 10;
        goto NEXT;
    OP(pushcompsc): {
        MVMObject * const sc  = GET_REG(cur_op, 0).o;
        if (REPR(sc)->ID != MVM_REPR_ID_SCRef)
            MVM_exception_throw_adhoc(tc, "Can only push an SCRef with pushcompsc");
        if (MVM_is_null(tc, tc->compiling_scs)) {
            MVMROOT(tc, sc, {
                tc->compiling_scs = MVM_repr_alloc_init(tc, tc->instance->boot_types.BOOTArray);
            });
        }
        MVM_repr_unshift_o(tc, tc->compiling_scs, sc);
        cur_op += 2;
        goto NEXT;
    }
}

```

## MVM_interp_run

- Cの実装の場合, switch文に展開される可能性がある為, 命令ディスパッチが書かれているCソース・ファイルの指定の場所にのみ処理を記述せざるを得ない
    - その為, 1ファイルあたりの記述量が膨大になり, 命令のモジュール化ができない
- Threaded Codeの実装を考えた場合, この命令に対応して大幅に処理系の実装を変更する必要がある．
- デバッグ時には今どの命令を実行しているか, ラベルテーブルを利用して参照せざるを得ず, 手間がかかる．

## NQP
- MoarVM, JVM上で動作する Perl6のサブセットとなっている．
- NQPの基本文法はPerl6に準拠しているが, 束縛ベースで変数を利用するなどいくつか異なる点が存在する．
- NQPは最終的にブートストラップを行う処理系であるが, 初回のビルド時には, すでに書かれたMoarVM, JVMのバイトコードを必要とする．
    - この状態をStage0といい, Stage0を利用してStage1, Stage1を利用してStage2をビルドする事で完成する．
- NQPの実行可能なインタプリタである`nqp`は, MoarVMの実行バイナリ`moar` にライブラリパスなどを設定し, ビルドしたライブラリなどを引数として渡すシェルスクリプトとなっている．
- `nqp` を実行する事でREPLが起動され, NQPスクリプトを `nqp` に入力として与える事で, 通常のスクリプト言語の様に実行する事が可能となる．
- NQPの設計はRoastで定義されているPerl6とは異なり, 今後も変化していく事が公表されている．

```
#! nqp

sub fib($n) {
    $n < 2 ?? $n !! fib($n-1) + fib($n - 2);
}

my $N := 29;

my $z  := fib($N);

say("fib($N) = " ~ fib($N));
```

## CbCによるMoarVM

- MoarVMの中心部分はバイトコードを解釈するバイトコードインタプリタである．
- その為, CbCを用いてMoarVMのバイトコードインタプリタ部分の書き換えを検討する．

## CbCMoarVMのバイトコードディスパッチ

- interp.cではマクロを利用した cur_op (現在のオペコード) の計算及び, マクロ遷移かswitch文を利用して次の命令列に遷移していた
- CbCMoarVMでは, それぞれの命令に対応するCodeGearを生成し, このCodeGearの集合であるテーブルCODESを作成した
- このテーブルは`cbc_next`というCodeGearから参照し, 以降はこのCodeGearの遷移として処理が継続される．

```
#define NEXT_OP(i) (i->op = *(MVMuint16 *)(i
    ->cur_op), i->cur_op += 2, i->op)
#define DISPATCH(op) {goto (CODES[op])(i);}
#define OP(name) OP_ ## name
#define NEXT(i) CODES[NEXT_OP(i)](i)
static int tracing_enabled = 0;

_code cbc_next(INTERP i){
    goto NEXT(i);
}
```

```
__code (* CODES[])(INTERP) = {
  cbc_no_op,
  cbc_const_i8,
  cbc_const_i16,
  cbc_const_i32,
  cbc_const_i64,
  cbc_const_n32,
  cbc_const_n64,
  cbc_const_s,
  cbc_set,
  cbc_extend_u8,
  cbc_extend_u16,
```

## CodeGearの入出力インターフェイス

- MoarVMではレジスタの集合や命令列などをMVM_interp_runのローカル変数として利用し, 各命令実行箇所で参照している
- CodeGearに書き換えた場合, このローカル変数にはアクセスする事が不可能となる．
- その為, 入出力としてMoarVMの情報をまとめた構造体interpのポインタであるINTERPを受け渡し, これを利用してアクセスする


```
typedef struct interp {
    MVMuint16 op;
     /* Points to the place in the bytecode
         right after the current opcode. */
     /* See the NEXT_OP macro for making sense
          of this */
    MVMuint8 *cur_op;
     /* The current frame’s bytecode start. */
    MVMuint8 *bytecode_start;
     /* Points to the base of the current
         register set for the frame we
     * are presently in. */
    MVMRegister *reg_base;
     /* Points to the current compilation unit
         . */
    MVMCompUnit *cu;
     /* The current call site we’re
         constructing. */
    MVMCallsite *cur_callsite;
    MVMThreadContext *tc;
 } INTER,*INTERP;
```

## DataGearへの変換

- バイトコードに対応する命令をそれぞれCodeGearに変換していく．
- `OP(.*)`の`(.*)`の部分をCodeGearの名前として先頭に `cbc_` をつけた上で設定する．
- cur_opなどはINTERPを経由してアクセスする様に修正する．
- 末尾の `NEXT` を次のCodeGearにアクセスする為に `cbc_next` に修正する．
- case文で次のcase文に流れる箇所は, 直接その下のcase文に該当するCodeGearに遷移する．

- 論文執筆時はstaticに修正する必要があったが, その後CbCコンパイラの改良により不要となった．

```
__code cbc_no_op(INTERP i){
    goto cbc_next(i);
}
__code cbc_const_i8(INTERP i){
    goto cbc_const_i16(i);
}
__code cbc_const_i16(INTERP i){
    goto cbc_const_i32(i);
}
__code cbc_const_i32(INTERP i){
    MVM_exception_throw_adhoc(i->tc, "const_iX NYI");
   goto cbc_const_i64(i);
}
__code cbc_const_i64(INTERP i){
    GET_REG(i->cur_op, 0,i).i64 = MVM_BC_get_I64(i->cur_op, 2);
    i->cur_op += 10;
    goto cbc_next(i);
}
__code cbc_pushcompsc(INTERP i){
    MVMObject * sc;
    sc  = GET_REG(i->cur_op, 0,i).o;
    if (REPR(sc)->ID != MVM_REPR_ID_SCRef)
        MVM_exception_throw_adhoc(i->tc, "Can only push an SCRef with pushcompsc");
    if (MVM_is_null(i->tc, i->tc->compiling_scs)) {
        MVMROOT(i->tc, sc, {
            i->tc->compiling_scs = MVM_repr_alloc_init(i->tc, i->tc->instance->boot_types.BOOTArray);
        });
    }
    MVM_repr_unshift_o(i->tc, i->tc->compiling_scs, sc);
    i->cur_op += 2;
    goto cbc_next(i);
}
```

## MoarVMのデバッグ手法

- MoarVMはバイトコードをランダムに生成する仕様となっている
    - 一旦moarvmバイトコードとして出力したファイルを実行する場合は同じ処理内容となっている
- そのため, MoarVMのデバッグは同じバイトコードを入力として与え, オリジナルのMoarVMと並列してgdbを用いてトレースを行う．
- この際, 実行するバイトコードの数が膨大となるので, scriptコマンドを用いて実行するバイトコードの番号を吐き出し, ログファイルを用いて比較する．

## MoarVMのデバッグ時のbreak point

- CbC側では次のオペコードの遷移は `cbc_next` というCodeGearで行う
- CodeGearは関数として扱える為, これに直接break pointを設定する

```
(gdb) b cbc_next
Breakpoint 2 at 0x7ffff7560288: file src/core
     /cbc-interp.cbc, line 61.
(gdb) command 2
Type commands for breakpoint(s) 2, one per
     line.
End with a line saying just "end".
>p CODES[*(MVMuint16 *)i->cur_op]
>p *(MVMuint16 *)i->cur_op
>c
>end
```
- オリジナルの場合マクロである為, dummy関数をマクロに記述し, この関数にbreakpointを設定する

```
dalmore gdb --args ../../MoarVM_Original/
     MoarVM/moar --libpath=src/vm/moar/stage0
     gen/moar/stage1/nqp
(gdb) b dummy
Function "dummy" not defined.
Make breakpoint pending on future shared
     library load? (y or [n]) y
Breakpoint 1 (dummy) pending.
(gdb) command 1
Type commands for breakpoint(s) 1, one per
     line.
End with a line saying just "end".
>up
>p *(MVMuint16 *)(cur_op)
>c
>end
```

## MoarVMのトレース

- トレース時には次の様なデバッグ情報の表示を利用する
- デバッガに, breakpointで停止した際のcur_opの値を表示する様に設定する．

```
Breakpoint 1, dummy () at src/core/interp.c
     :46
46 }
#1 0x00007ffff75608fe in MVM_interp_run (tc=0
     x604a20,
    initial_invoke=0x7ffff76c7168 <
        toplevel_initial_invoke>, invoke_data
        =0x67ff10)
    at src/core/interp.c:119
119 goto NEXT;
$1 = 159
Breakpoint 1, dummy () at src/core/interp.c
     :46
46 }
#1 0x00007ffff75689da in MVM_interp_run (tc=0
     x604a20,
    initial_invoke=0x7ffff76c7168 <
        toplevel_initial_invoke>, invoke_data
        =0x67ff10)
    at src/core/interp.c:1169
1169 goto NEXT;
$2 = 162
```
## MoarVMのデバッグ

- cur_opのみをPerlスクリプトなどを用いて抜き出し, 並列にログを取得したオリジナルと差分を図る
- この際に差異が発生したオペコードを確認し, その前の状態で確認していく

```
131 : 131
139 : 139
140 : 140
144 : 144
558 : 558
391 : 391
749 : 749
53 : 53
*54 : 8
```
## 現在のCbCMoarVM

- 現在はNQP, Rakudoのセルフビルドが達成でき, オリジナルと同等のテスト達成率を持っている
- moarの起動時のオプションとして `--cbc` を与えることによりCbCで動き, そうでない場合は通常のCで記述された箇所で実行される

## CbCMoarVMの利点

- バイトコードインタプリタの箇所をモジュール化する事が可能となり, CodeGearの再利用性や記述生が高まる
- デバッグ時にラベルではなくCodeGearにbreakpointを設定可能となり，デバッグが安易となる
- ThreadedCodeを実装する場合, CodeGearを組み合わせることにより実装する事が可能となる

## CbCMoarVMの欠点

- CbCコンパイラがバグを発生させやすく, 意図しない挙動を示す事がある
- MoarVMのオリジナルの更新頻度が高い為, 追従していく必要がある
- CodeGear側からCに戻る際に手順が複雑となる
- CodeGearを単位として用いる事で複雑なプログラミングが要求される.

## CbCMoarVMと通常のMoarVMの比較

- CbCMoarVMと通常のMoarVMの速度比較を行った

```
#! nqp
# Example of a while loop

my $i := 0;
while $i < 10 {
    say("i={$i++}");
}
```

```
subset Fizz of Int where * %% 3;
subset Buzz of Int where * %% 5;
subset FizzBuzz of Int where Fizz&Buzz;
subset Number of Int where none Fizz|Buzz;

proto sub fizzbuzz ($) { * }
multi sub fizzbuzz (FizzBuzz) { "FuzzBuzz" }
multi sub fizzbuzz (Fizz) { "Fizz" }
multi sub fizzbuzz (Buzz) { "Buzz" }
multi sub fizzbuzz (Number $number) { $number }

fizzbuzz($_).say for 1..15;

```