LoginSignup
6
4

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

Perl 5Advent Calendar 2016Day 6
@mackee_w

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

Posted at

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

この記事はPerl 5 Advent Calendar 2016 6日目の記事です。

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

ELVMとは

ELVM Compiler Infrastructure

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

また、C++のconstexprを用いたコンパイル時Cコンパイラ(????)を実装した方も現れました。
コンパイル中にコンパイルする「コンパイル時Cコンパイラ」をつくった話

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

ELVM で C コンパイラをポーティングしてみよう（Vim script 編）

やったこと

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

$ 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が入っているかを判別し小分けされたサブルーチンを実行する
  1. 最後にexit;が来て終了

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

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

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

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

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

$ 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倍の時間を食います。またテストケースではメモリ領域のここまで大きく使うことはないので、逐次確保するようにしました。

  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 での変更点

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というなるほどナァという記述があったのでパクりました。

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使ったりもしましたが、結局warnで$pcを表示してループしているところを見つけて生成されたコードを読む方が早かったです。

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

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

$ 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)だと

$ 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だと

$ 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に置き換えてみました。

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();
}

そうすると

./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に収めるとどうか。

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();
}

./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 のサブルーチン

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

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

$ 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さんによる「「基本的な知識だけでこんなの作れます」というサンプルを紹介します」です。

6
4
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
6
4

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?