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


## 研究目的
- 現在開発されているPerl6の実装にRakudoがあり, RakudoはNQP(Perl6のサブセット)で記述されたPerl6, NQPで記述されたNQPコンパイラ, NQPを解釈するVMで構成されている
- NQPコンパイラはRakudoのVMであるMoarVM用のバイトコードを生成し, MoarVMはこのバイトコードを解釈, 実行する
- Continuation based C (CbC)という言語は継続を基本とするC言語であり, 言語処理系に応用出来ると考えられる
- スクリプ言語などは, バイトコードを扱うが, この実行にcae文や, ラベルgotoなどを利用しており, この部分はCbCの機能で書き換える事が可能である
- 従って, CbC一部用いてPerl6にC処理系であるMoarVMの書き換えを行い, 処理を検討する．
![](fig/perl6nqp.svg)
- (Rakudoの構成図)

## Continuation Based C (CbC)
- Continuation Based C (CbC) はCodeGearを単位として用いたプログラミング言語である.
- CodeGearはCの通常の関数呼び出しとは異なり，スタックに値を積まず, 次のCodeGearにgoto文によって遷移する.
- CodeGearはCの関数宣言の型名の代わりに`__code`と書く事で宣言出来る．
- CodeGearの引数は, 各CodeGearの入出力として利用する．

```
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は現在3種類の実装がある．
  - gcc (version 9.0.0)
  - llvm/clang (version 7.0.0)
  - micro-c

## 言語処理系の応用
- スクリプト言語処理系は, バイトコードにコンパイルされ, バイトコードをJITを用いてネイティブに変換する
- JITを使わない場合, バイトコードに対応した, case文や, ラベルのテーブルにgotoすることで処理を実行する
- CbCを言語処理系に応用した場合, バイトコードに対応するCodeGearを生成することが可能である
- バイトコードに対応したCodeGearは, CodeGearのテーブルを経由することで実行出来る
- CodeGearに分割することで, 処理を複数の関数で記述する事が出来, ファイル分割などのモジュール化が可能となる

## Rakudo
- Rakudoとは現在のPerl6の主力な実装である．
- 実行環境のVM, Perl6のサブセットであるNQP(NotQuitPerl), NQPで記述されたPerl6(Rakudo)という構成になっている．
- コンパイラは, NQPで記述されたPerl6コンパイラ, NQPで記述されたNQPコンパイラ, MoarVMバイトコードを解釈するMoarVMという構成である


<img src="fig/tgraph/1.svg" alt=""  width="50%" height="50%"/>


## MoarVM

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

- マクロDISPATCHで, ラベルgotoかcase文に, バイトコードに対応した処理を行う
    - この中の `OP` で宣言されたブロックがそれぞれバイトコードに対応する処理となっている．
- この中では `GET_REG` などのマクロを用いてMoarVMのレジスタにアクセスする．
- `cur_op`は次のバイトコード列が登録されており, マクロ `NEXT` で決められた方法で次のバイトコードに対応した処理に遷移する．

```
DISPATCH(NEXT_OP) {
    OP(const_i64):
        GET_REG(cur_op, 0).i64 = MVM_BC_get_I64(cur_op, 2);
        cur_op += 10;
        goto NEXT;
}

```

## MVM_BC_get_I64の実装

```
 MVM_STATIC_INLINE MVMint64 MVM_BC_get_I64(const MVMuint8 *cur_op, int offset) {
     const MVMuint8 *const where = cur_op + offset;
 #ifdef MVM_CAN_UNALIGNED_INT64
     return *(MVMint64 *)where;
 #else
     MVMint64 temp;
     memmove(&temp, where, sizeof(MVMint64));
     return temp;
 #endif
 }
```

## MVM_interp_runで使用されているマクロ

```
DISPATCH(NEXT_OP) {
    OP(const_i64):
```

- マクロ `DISPATCH` 及び `OP` は次の様に定義している

```
 #define OP(name) OP_ ## name
 #define NEXT *LABELS[NEXT_OP]
```

- マクロ`DISPATCH`は, ラベルgotoが利用できる場合は無視される
- マクロ `OP` が, 対応するバイトコード命令を, ラベル列に変換する


```
    OP_const_i16:
    OP_const_i32:
        MVM_exception_throw_adhoc(tc, "const_iX NYI");
    OP_const_i64:
```

## MVM_interp_runのマクロ

- MVM_interp_runではマクロを利用してMoarVMの環境などにアクセスしている
-  頻出するマクロに `GET_REG` があり, 次のような使い方をする

```
    OP(const_i64):
        GET_REG(cur_op, 0).i64 = MVM_BC_get_I64(cur_op, 2);
        cur_op += 10;
```


- `GET_REG`はバイトコードに埋められた数値を利用して, レジスタ情報を取得/設定などをする
- `GET_REG`は次の様に展開される

```
        reg_base[*((MVMuint16 *)(cur_op + 0))].i64 = MVM_BC_get_I64(cur_op, 2);
```

- `reg_base` はMoarVMの現在のフレームのレジスタ情報が保存されたポインタであり, MVM_interp_runではローカル変数として利用している

## MVM_interp_runで使用されているマクロ

- 次のバイトコード命令に遷移するマクロ `NEXT` は, ラベルgotoが使用可能な場合次の様に記述されている
- `NEXT`自体はラベルテーブルにアクセスし, ラベルを取り出す
- 次のバイトコードを取り出すのは, `NEXT_OP` というマクロが担っている

```
#define NEXT_OP (op = *(MVMuint16 *)(cur_op), cur_op += 2, op)
#define NEXT *LABELS[NEXT_OP]

```
- マクロ `NEXT` は次の様に展開される

```
goto *LABELS[(op = *(MVMuint16 *)(cur_op), cur_op += 2, op)];
```


## 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

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



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

- CbCをMoarVMに適応すると, ラベルなどで制御していた命令に対応する処理をCodeGearで記述する事が可能である
- オリジナルでは, マクロ `NEXT` が担当していた, 次のバイトコードへの移動は, NEXT相当のCodeGear `cbc_next`で処理を行う
- CodeGearの入出力として, MoarVMなどの情報をまとめた構造体を利用する

```
__code cbc_next(INTERP i){
    __code (*c)(INTERP)
    c = CODES[(i->op = *(MVMuint16 *)(i->cur_op), i->cur_op += 2, i->op)]; // c = NEXT(i)
    goto c(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);
}

```

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

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


```
typedef struct interp {
    MVMuint16 op;
    MVMuint8 *cur_op;
    MVMuint8 *bytecode_start;
    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;
```

## CbCMoarVMのCodeGearテーブル

- CodeGearテーブルは引数としてINTERを受け取るCodeGearの配列として定義する


```
__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,
```


## NQP
- Perl6の機能を制約したプログラミング言語であり, Perl6はNQPで記述されている
    - その為Perl6処理系は, NQPの動作を目的に実装することでPerl6の動作が可能となる
    - NQPコンパイラ自身もNQPで記述されている
- Perl6と違い, 変数の宣言を `:=` を利用した束縛で行う, `++` 演算子が使用できないなどの違いがある
- nqpのオペコードを利用する際に,型を指定する事が可能である

```
sub add_test(int $n) {
    my $sum := 0;
    while nqp::isgt_i($n,1) {
        $sum := nqp::add_i($sum,$n);
        $n := nqp::sub_i($n,1);
    }
    return $sum;
}

say(add_test(10));
```

## NQPのバイトコード

- NQPはMoarVMのバイトコードにコンパイルし, バイトコードをファイルに保存することが可能である
- MoarVMのバイトコードは, アセンブリの様にダンプする事が可能である
- 実際に先程のコードをバイトコードにコンパイルし, 対応するバイトコードをダンプすると次の様に表示される


```
     annotation: hoge.nqp:3
     label_1:
00007      const_i64_16       loc_2_int, 1
00008      gt_i               loc_2_int, loc_0_int, loc_2_int
00009      unless_i           loc_2_int, label_2(00022)
00010      osrpoint
     annotation: hoge.nqp:4
00011      decont             loc_3_obj, loc_1_obj
00012      smrt_numify        loc_4_num, loc_3_obj
00013      coerce_ni          loc_5_int, loc_4_num
00014      add_i              loc_5_int, loc_5_int, loc_0_int
00015      hllboxtype_i       loc_3_obj
00016      box_i              loc_3_obj, loc_5_int, loc_3_obj
00017      set                loc_1_obj, loc_3_obj
     annotation: hoge.nqp:5
00018      const_i64_16       loc_5_int, 1
00019      sub_i              loc_5_int, loc_0_int, loc_5_int
00020      set                loc_0_int, loc_5_int
00021      goto               label_1(00007)
```

## NQPのバイトコードとCbC

- NQPが生成したMoarVMバイトコードは確実に次に実行される命令がある箇所が複数存在する
- 静的にCのソースファイルに, NQPが生成したバイトコードと対応するCbCのCodeGearの実行を書くことで決定的に命令を実行可能でえある．

## CbCMoarVMの利点

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

## CbCMoarVMの欠点

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



## 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=0x604a20,
    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=0x604a20,
    initial_invoke=0x7ffff76c7168 <toplevel_initial_invoke>, invoke_data=0x67ff10)
    at src/core/interp.c:1169
1169	                goto NEXT;
$2 = 162
```

## CbCMoarVMのデバッグ

```
Breakpoint 2, cbc_next (i=0x7fffffffdc30) at src/core/cbc-interp.cbc:61
61	    goto NEXT(i);
$1 = (void (*)(INTERP)) 0x7ffff7566f53 <cbc_takeclosure>
$2 = 162

Breakpoint 2, cbc_next (i=0x7fffffffdc30) at src/core/cbc-interp.cbc:61
61	    goto NEXT(i);
$3 = (void (*)(INTERP)) 0x7ffff7565f86 <cbc_checkarity>
$4 = 140

Breakpoint 2, cbc_next (i=0x7fffffffdc30) at src/core/cbc-interp.cbc:61
61	    goto NEXT(i);
$5 = (void (*)(INTERP)) 0x7ffff7579d06 <cbc_paramnamesused>
$6 = 558


```

## 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で記述された箇所で実行される
- Perl6の実行バイナリperl6, NQPの実行バイナリnqp は, それぞれmoarを起動するシェルスクリプトである為, `--cbc` オプションをシェルスクリプト内に書き加えることで, Perl6, NQPがそれぞれCbCで起動する

```
#!/bin/sh
exec /mnt/dalmore-home/one/src/Perl6/Optimize/llvm/build_perl6/bin/moar --cbc \
     --libpath=/mnt/dalmore-home/one/src/Perl6/Optimize/llvm/build_perl6/share/nqp/lib \
     /mnt/dalmore-home/one/src/Perl6/Optimize/llvm/build_perl6/share/nqp/lib/nqp.moarvm "$@"
```

## ThreadedCodeの実装

- MoarVM内のオペコードに対応する処理が分離出来たことにより, オペコードに該当するCodeGearを書き連ねることによってThreadedCodeが実装可能となる


## CbCMoarVMと通常のMoarVMの比較

- CbCMoarVMと通常のMoarVMの速度比較を行った
- 対象として, 単純なループで数値をインクリメントする例題と, フィボナッチ数列を求める例題を選択した
- NQPで実装した場合とPerl6で実装した場合の速度を計測した

```
#! nqp

my $count := 100_000_000;

my $i := 0;

while ++$i <= $count {
}
```

```
#! nqp

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

my $N := 30;

my $z  := fib($N);

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

```
## フィボナッチの例題

- オリジナル
    - 1.379 sec
    - 1.350 sec
    - 1.346 sec
- CbCMoarVM
    - 1.636 sec
    - 1.804 sec
    - 1.787 sec
- フィボナッチの例題ではCbCMoarVMが劣る結果となった


## 単純ループ

- オリジナル
    - 7.499 sec
    - 7.844 sec
    - 6.746 sec
- CbCMoarVM
    - 6.135 sec
    - 6.362 sec
    - 6.074 sec

- 単純ループではCbCMoarVMの方が高速に動作する場合もある


## 基本ブロックとCodeGear

- コンパイラなどでは, 関数あるいはループの先頭から, 別の関数呼び出し, あるいはジャンプするまでの間のコードを基本ブロックと呼ぶ
- 基本ブロックは入力に影響を受けず, 基本ブロックが決定したタイミングである決定的な処理を行う
- 予め実行する基本ブロックが確定していれば, その部分のみ抜き出してコンパイルする事が可能である
- CbCのCodeGearは, この基本ブロックとみなす事が可能である
- その為, NQPの例題の様に, 予め実行する基本ブロックが確定すれば, その部分の処理が可能となる
- これを行うことで, CbCを用いてMoarVMのThreadedCode実装が可能となる

```
__code cbc_const_i64(INTERP i,__code cbc_next(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);
}

goto cbc_const_i64_16(i,cbc_gt_i_01);

__code cbc_gt_i_01(INTERP i){
	goto cbc_gt_i(i,cbc_unless_i_01);
}

__code cbc_unless_i_01(INTERP i,cbc_osrpoint_01){
	goto cbc_unless_i(i,cbc_osrpoint_01);
}
```


## まとめと今後の課題
- 継続と基本としたC言語 Continuation Based Cを用いてPerl6の処理系の一部を書き直した
- CbCの持つCodeGearによって, 本来はモジュール化出来ない箇所をモジュール化する事が出来た
- MoarVMの速度改善にはThreadedCodeが期待でき, CodeGearベースの命令ディスパッチとThreadedCodeは相性が良いと考えられる
- 今後は実行するバイトコードによりThreadedCode箇所と通常の配列を読み取り, 次のCodeGearを計算する処理を両立させていく