Perl 5版のELVMバックエンドを実装する

こんにちは。みなさまよいPerlライフをお過ごしでしょうか。

この記事は[Perl 5 Advent Calendar 2016](http://qiita.com/advent-calendar/2016/perl5) 6日目の記事です。

昨日はskajiさんによる[Perl+Mojoでイベント駆動プログラミング](Perl+Mojoでイベント駆動プログラミング)でした。

## ELVMとは

[ELVM Compiler Infrastructure](http://shinh.hatenablog.com/entry/2016/10/18/095437)

EsoLang Virtual Machineの略で、C言語で書かれたプログラムをELVM IRという中間形式に変換した後に、それを元に多言語にトランスパイルするものです。EsoLang(難解プログラミング言語)というのがついているとおり、、BrainfuckやUnlambdaなどの難解プログラミング言語でのバックエンド実装があります。特にこの記事で書かれているCコンパイラ(8cc)をpietという画像がソースコードになるプログラミング言語に変換するの図は圧巻ですね。

また、C++の`constexpr`を用いたコンパイル時Cコンパイラ(????)を実装した方も現れました。
[コンパイル中にコンパイルする「コンパイル時Cコンパイラ」をつくった話](http://kw-udon.hatenablog.com/entry/2016/12/03/201722)

私は、~~難解プログラミング言語の一つ~~VimScriptでバックエンドを実装した話を見かけて~~よく知られている難解プログラミング言語の一つ~~であるPerl 5の実装がないことを知りこのビッグウェーブ:surfer:に乗ろうと実装した次第であります。

[ELVM で C コンパイラをポーティングしてみよう（Vim script 編）](http://rhysd.hatenablog.com/entry/2016/12/02/030511)

## やったこと

以上の記事を参考にやってみました。具体的には

```bash
$ git clone https://github.com/shinh/elvm
$ cd elvm
$ cp target/rb.c target/pl.c
```

とRubyのバックエンドのコードから1対1の訳を作ろうとした感じです。

## 困ったこと

ELVMのやっていることとしては、詳しくは以上の記事を参考にしてもらうとして、処理の流れとしては簡単にいえばこうなります。

1. 初期化処理(7つのレジスタの初期化、メモリ領域`@mem`の初期化)
2. プログラムカウンタ`$pc`を増減しながら命令を逐次実行
 - ただし命令は512個ごとに関数に分割されている。一番外側のループでどの領域に`$pc`が入っているかを判別し小分けされたサブルーチンを実行する
3. 最後に`exit;`が来て終了

この1.の初期化処理がネックであり、Rubyなどでは

```ruby
@mem = [0] * (1 << 24)
```

というふうになっています。これをPerlでやるとすれば

```perl
my @mem = ((0) x (1 << 24));
```

というふうになります。がこれは問題です。

```bash
$ ruby --version
ruby 2.3.1p112 (2016-04-26 revision 54768) [x86_64-darwin14]
$ time ruby -e '@mem = [0] * (1 << 24)'
ruby -e '@mem = [0] * (1 << 24)'  0.09s user 0.10s system 80% cpu 0.234 total

$ perl -v
This is perl 5, version 24, subversion 0 (v5.24.0) built for darwin-2level
$ time perl -E 'my @mem = ((0) x (1 << 24));'
perl -E 'my @mem = ((0) x (1 << 24));'  0.61s user 0.22s system 98% cpu 0.844 total
```

Rubyに比べて6倍の時間を食います。またテストケースではメモリ領域のここまで大きく使うことはないので、逐次確保するようにしました。

```c
  case LOAD:
    emit_line("%s = ($mem[%s] //= 0);", reg_names[inst->dst.reg], src_str(inst));
    break;
```

defined-orにしているのはundefが入った場合に比較演算子などでwarningが出るケースがあるからです。
これはRubyやPythonでは起こらなくて、というかPythonとかRubyは確保されていないところにアクセスすると`index out of range`になってしまうのですが。あと`nil == true`や`None == True`はFalseがちゃんと返ります。

後から指摘されたことですがメモリに空文字が入ることはないので`||= 0`の形で良さそうです。

また実装すべき命令としては22個あります。中には比較命令やジャンプ命令もあります。
比較命令はrubyなどで使われているユーティリティ関数を用いることで演算子を含んだ形式に変換されるのでそのまま利用可能です。Perlは文字列での比較と数値での比較とで2種類の演算子がありますが、ELVMでは文字列としての比較は行われないので特に配慮はしていません。

あとプログラムカウンタに対応する命令を実行する際にRubyではcase文を使っていますが、Perlではswitchやパターンマッチに相当する構文はありません。「いや、given-whenが……」と言いかけたあなた、彼については一旦忘れましょう。

[perl5180delta - perl v5.18.0 での変更点](http://perldoc.jp/docs/perl/5.18.0/perl5180delta.pod#The32smartmatch32family32of32features32are32now32experimental)

> v5.10.0 で追加され、v5.10.1 で大きく改訂されたスマートマッチングは、 いつも不満な点でした。 これを有用にする方法はいくつかありますが、問題があり、Perl のユーザーと 実装者の両方を混乱させることがわかっています。 この問題をもっともよく対処するための多くの提案がありました。 **スマートマッチングは将来変更されるか削除されることはほぼ確実です。** 現在の振る舞いに依存することは勧められません。

なので`if-elsif`で実装することにしました。幸いなことにPythonも同じ仲間です。親近感が湧いてきます。

RubyやPythonの実装では

1. `pl_emit_func_prologue` funcの宣言と初期化とループの開始
2. `pl_emit_pc_change` プログラムカウンタに対応した命令の記述 1個目
3. `pl_emit_pc_change` プログラムカウンタに対応した命令の記述 2個目

...

N. `pl_emit_func_epilogue` ループの終了とfuncの終了

となっており、`pl_emit_pc_change`の繰り返しで命令が連なります。構文的な問題ですが、Rubyの`case`だと閉じカッコや`end`的なものが要らないのですが、Perlの`if`はそうはいきません。また、`pl_emit_pc_change`の中で自分がfuncの中で何個目の命令かを知るすべがないので`if`と`elsif`の出し分けも難しそうです。
そこでPythonの実装を見てみると`if False: pass`というなるほどナァという記述があったのでパクりました。

```c
static void pl_emit_func_prologue(int func_id) {
  emit_line("");
  emit_line("sub func%d {", func_id);
  inc_indent();
  emit_line("while (%d <= $pc && $pc < %d) {",
            func_id * CHUNKED_FUNC_SIZE, (func_id + 1) * CHUNKED_FUNC_SIZE);
  inc_indent();
  emit_line("if (0) {");
  inc_indent();
}

static void pl_emit_func_epilogue(void) {
  dec_indent();
  emit_line("}");
  emit_line("$pc++;");
  dec_indent();
  emit_line("}");
  dec_indent();
  emit_line("}");
}

static void pl_emit_pc_change(int pc) {
  dec_indent();
  emit_line("}");
  emit_line("elsif ($pc ==  %d) {", pc);
  inc_indent();
}
```

## バグフィックス

以上とあと少々のバグフィックスを行ってテストが全部通る状態になりました。

途中無限ループに陥ることがありなんでやと調べたのですが、無駄に[gdbperl](https://github.com/ahiguti/gdbperl)使ったりもしましたが、結局warnで`$pc`を表示してループしているところを見つけて生成されたコードを読む方が早かったです。

## チューニングできなかった話

そんなわけでテストが通って速度的にはどんなもんやろと調べました。

```bash
$ time ./runtest.sh out/8cc.c.eir.pl.out perl out/8cc.c.eir.pl
./runtest.sh out/8cc.c.eir.pl.out perl out/8cc.c.eir.pl  4.22s user 0.11s system 99% cpu 4.367 total
```

これがどんなもんかというと同じPCのRuby(2.3.1)だと

```bash
$ time ./runtest.sh out/8cc.c.eir.rb.out ruby out/8cc.c.eir.rb
./runtest.sh out/8cc.c.eir.rb.out ruby out/8cc.c.eir.rb  0.50s user 0.14s system 93% cpu 0.685 total
```

その差8倍強……！

しかしこれがperl 5.20.3だと

```bash
$ perl -v
This is perl 5, version 20, subversion 3 (v5.20.3) built for darwin-2level
$ time ./runtest.sh out/8cc.c.eir.pl.out perl out/8cc.c.eir.pl
./runtest.sh out/8cc.c.eir.pl.out perl out/8cc.c.eir.pl  2.45s user 0.10s system 99% cpu 2.562 total
```

と差が縮まります。手元にあった5.16環境も5.20と同じぐらいだったので5.22もしくは5.24で何かあったんですかね……。

### if-elsifを`goto LABEL`で置き換えてみる

`if-elsif`は線形探索のような気がしたので`goto LABEL`に置き換えてみました。

```c
static void pl_emit_func_prologue(int func_id) {
  emit_line("");
  emit_line("sub func%d {", func_id);
  inc_indent();
  emit_line("BEGIN:");
  inc_indent();
  emit_line("goto END unless (%d <= $pc && $pc < %d);",
            func_id * CHUNKED_FUNC_SIZE, (func_id + 1) * CHUNKED_FUNC_SIZE);
  emit_line("goto \"PC$pc\";");
}

static void pl_emit_func_epilogue(void) {
  emit_line("$pc++;");
  emit_line("goto BEGIN;");
  dec_indent();
  emit_line("END:");
  dec_indent();
  emit_line("}");
}

static void pl_emit_pc_change(int pc) {
  emit_line("$pc++;");
  emit_line("goto BEGIN;");
  dec_indent();
  emit_line("PC%d:", pc);
  inc_indent();
}
```

そうすると

```bash
./runtest.sh out/8cc.c.eir.pl.out perl out/8cc.c.eir.pl  25.98s user 0.12s system 99% cpu 26.114 total
```

つら〜〜〜なんじゃこりゃ。ラベルの探索は遅いんですかね……。ちょっと不思議でした。

### if-elsifを`$hash{$pc} = <coderef>`で置き換えてみる

では次は命令をcoderefにしてhashに収めるとどうか。

```c
static void pl_emit_func_prologue(int func_id) {
  emit_line("");
  emit_line("sub func%d {", func_id);
  inc_indent();
  emit_line("my $func_id = %d;", func_id);
  emit_line("my %%pc_subs = (");
  inc_indent();
  emit_line("dummy => sub {");
  inc_indent();
}

static void pl_emit_func_epilogue(void) {
  dec_indent();
  emit_line("},");
  dec_indent();
  emit_line(");");
  emit_line("while (%d * $func_id <= $pc && $pc < ($func_id + 1) * %d) {",
             CHUNKED_FUNC_SIZE, CHUNKED_FUNC_SIZE);
  inc_indent();
  emit_line("goto $pc_subs{$pc}->();");
  emit_line("$pc++");
  dec_indent();
  emit_line("}");
  dec_indent();
  emit_line("}");
}

static void pl_emit_pc_change(int pc) {
  dec_indent();
  emit_line("},");
  emit_line("%d => sub {", pc);
  inc_indent();
}
```

```bash
./runtest.sh out/8cc.c.eir.pl.out perl out/8cc.c.eir.pl  80.06s user 0.29s system 99% cpu 1:20.57 total
```

もっとつらくなった。不思議ですね。

### インライン展開

インライン展開すればいいんじゃないか、そういえばPerlには定数関数というものがあり、、、

[perlsub - Perl のサブルーチン](http://perldoc.jp/docs/perl/5.20.1/perlsub.pod#Constant32Functions)

> () というプロトタイプを持った関数はインライン展開される可能性を 持っています。 最適化と定数畳み込み後の結果が一つの定数か、何のリファレンスも持たない レキシカルスコープのスカラであったならば、その関数が & を使わずに 呼びされたときに呼び出しのその場に置かれます。 

なるほどな？　しかし命令はレジスタというグローバル変数が縦横無尽に走っているのであまりこれには期待できないのでした。
ちなみに`$a = 1 - 1;`みたいなのはそのままでもちゃんと定数畳み込みされます。

```bash
$ perl -MO=Deparse -e '$a = 1 - 1;'                                                                                                                   $a = 0;
-e syntax OK
```

そう言えばそうだったなと思いつつ実際やってみたらおおっとなった事例でした。

### そもそも`$a`とか`$b`とかって

そういえば`$a`とか`$b`とかはソートにつかう変数だった……。今回はソートを使ってないのでセーフですが気をつけましょう。

## 意義と展望

- Perlはたいていの*NIXに入っているのでCコンパイラがなくても8ccをPerlにしたコードでその場でコンパイルできるのでは・・・！
  - すでにELVMバックエンドにはshellとかsedとか入っており勝てなさそう
- XSモジュールのPPを作るのに使えるか？　exportとかがめんどくさそうだけれど
- そもそもXSに変換したら良いのではと思ったけれど元がCなんだからそのままXSに出来た
- perlをPerlでビルドしたいけれど8ccでperlをコンパイルできるかな　と言うかめちゃくちゃ時間かかりそう


そんな感じで拙いチャレンジ記録でした。

明日はwakegiskyさんによる「「基本的な知識だけでこんなの作れます」というサンプルを紹介します」です。