PL_check とパトリオットミサイルのしくみ

perl memo

前回の記事はおかげさまで id:yappo さんに HE-N-TA-I 認定されたので安心してたら，マッチョな人に牛刀フラグを立てられ（もちろん冗談です*1），Shibuya.pm 入会への道もなかなか険しいなぁと思い知りました。

そんな空気は読まずに理論編？を Perl 5.8.8 のソースをもとに書いていきます。マニア向け。

Perl がスクリプトを実行するまで

perlguts の Compiled code セクションと Perl のソースコードをもとに，おおまかな実行機序を書いてみました。

  1. 字句解析器（レキサ; toke.c）
    • 字句エラーの検出
  2. 構文解析器（パーサ; perly.y*2）
    • 構文エラーの検出
    • OPCODE ツリーに変換; new*OP() in op.c
      • check ルーチンの実行（pass 1）
        • （文脈にもとづく）文法エラーの検出 by 各 PL_check[]()
        • 最適化: ボトムアップ by 各 PL_check[]()
      • 最適化: 不変値の定数化（pass 1a） by Perl_fold_constants() in op.c
    • 実行時コンテキスト((簡単には ARRAY コンテキストとか scalar コンテキストとかそういう奴です。))の伝播（pass 2）
      • 最適化: コンテキスト依存・トップダウン by （たとえば） Perl_scalar() in op.c
    • 「のぞき穴」式最適化（pass 3）
      • 最適化: 実行順にもとづく OPCODE 列 & 条件式 by Perl_peep() in op.c
  3. 実行 via runop() （たとえば）in run.c

最適化が随所に入るのでわかりにくくなってしまいました。要点だけ抜き出すと下記のようになります。

  1. ソースを読む
  2. 字句解析器
  3. 構文解析器
    1. OPCODE ツリーに変換
    2. (PL_check[o])() で文法チェック，OPCODE 変換
    3. 最適化
  4. 実行

ここには書いていませんが，Perl のやや特殊なところは，BEGIN {...} で定義された Perl コード部分がコンパイルフェーズとして随時実行されるところです((これが PL_compcv がレキサに影響を及ぼしているためなのか，PL_beginav でまとめといて全パース終了後に実行しているためなのかわかりませんでした。))。

自分用メモ（最適化にまつわる部分）
  1. PL_check[]() 時に周辺を最適化する（ボトム）
  2. new*OP() の最後で，「不変値になりそうな場合に即値に変換」チェックを実行（ややトップダウン的）
  3. 構文木をボトムアップに構築していって scalar など実行時コンテキストが確定した時点で，ツリーを下にたどっていって最適化（たとえば実行されないパスの削除 NULL-ify, op_next かっとび；トップダウン）
  4. なんらかの最上位（サブルーチンやファイル単位）に到達した際，実行順に OPCODE をたどって最適化

OPCODE の構造

op.h に定義されています。疑似コード((Java に見えますが気のせいです。public とか書いてないし。))で書いてみます。

class OP;

class BASEOP extends OP {
    OP      op_next;
    OP      op_sibling;
    method* op_ppaddr;
    OPCODE  op_type;
    U16     op_seq;
    U8      op_flags;
    U8      op_private;
}

/* 無引数 OPCODE */
class op extends BASEOP;

/* 1引数(単項演算) OPCODE */
class unop extends BASEOP {
    OP      op_first;
}

/* 2引数(二項演算) OPCODE */
class binop extends BASEOP {
    OP      op_first;
    OP      op_last;
}

/* 配列引数 OPCODE */
class listop extends BASEOP {
    OP      op_first;
    OP      op_last;
}

/*
    正規表現           OPCODE pmop
    制御構造(論理演算) OPCODE logop
    ループ構造         OPCODE loop
    ほか svop, padop, pvop は省略
 */

OPCODE type にまつわるグローバルデータ

opcode.h に定義されています。ヘッダファイルですが define 値によってかわるので，グローバル変数と思ってくれい。

/* opcode.h */

/*
    下2つはわかりやすくするために，
    わたしが typedef したものです
 */
typedef OP * (*PL_pp)(void);
typedef OP * (*PL_ck)(OP *);

/* 各 OPCODE の実行関数ポインタの集合 */
PL_pp PL_ppaddr[] = { ... };

/* 各 OPCODE の check 関数ポインタの集合 */
PL_ck PL_check[]  = { ... };

/* 各 OPCODE の名前と説明 */
char *PL_op_name[] = { ... };
char *PL_op_desc[] = { ... };
/* ですが以下のマクロを使うべき */
#define OP_NAME(o) ...
#define OP_DESC(o) ...

/* ↓についてはやや不明；なにかのフラグ？ */
U32 PL_opargs[] = { ... };

PL_pp タイプ((pp って perl program の略かと思ったら，push / pop の略でしたよ。))は引数 void，PL_ck タイプは OP * 1つになっていますが，実際にはそれぞれ先頭に Perl インタプリタのポインタ（pTHX）を渡すようになっています。わかりやすくするため省略しています（以下でも省略しています）。

以上を図示してみます。

OP のおもしろいところ 1: op_sibling

op_sibling によって片方向リスト構造をなしています。

たとえば listop の引数（を生成するため）の OPCODE 群を取得するためには，op_first を取得して，op_last に至るまで op_sibling をたぐっていけばよいことになります。listop だけでなく binop などについても設定されているので，どの OPCODE に対してもイテレータとしては op_sibling を使えば問題ない，ということです。

op_next は似たような名前ですが，実行順として次の OPCODE を示すポインタです。B::Concise でのツリー表示の末尾にある，「->3」みたいな数字と思えば結構です((まぁー実際問題 op_next は op_sibling と同じ値になることが多いですが，最適化すると，より「遠い」値になり得ます。とかいってわかったように書いてますが，推測に基づいて書いてます。))。

OP のおもしろいところ 2: op_ppaddr

op_ppaddr として上記の疑似コードでは下記のように書いていました。

method* op_ppaddr;

メソッドポインタであることを示すために method* と書いていますが，実際には

OP * (*op_ppaddr)(void);

のような定義となっています((先に書いたように，実際には void じゃないです。Perl インタプリタへのポインタをとります))。

おもしろいポイント 1

普通に考えれば，OP には OPCODE type が指定されているので，

    (*PL_ppaddr[o->op_type])();

のようにして OPCODE を実行すれば済むはずです。ですが，自分とこに op_ppaddr があるので，

    (*o->op_ppaddr)();

のように実行できます。Ruby でいう特異メソッドみたいですね。つまり，各 OPCODE インスタンスごとに実行する関数を変えられるのです。

おもしろいポイント 2

普通に考えれば，op_next というメンバがあるので

    for (OP *o = OP_START; o; o = o->op_next) {
        (*o->op_ppaddr)();
    }

のように実行すればいいはずです（もちろん条件式やループについては別に考えなくてはなりませんが）。しかし，op_ppaddr が指す関数は，次に実行する OPCODE を返すようになっています。


以上の OP の特性を生かして，runops() の通常版の実装*3は下記のようになっています。

int
Perl_runops_standard(pTHX)
{
    while ((PL_op = CALL_FPTR(PL_op->op_ppaddr)(aTHX))) {
        PERL_ASYNC_CHECK();
    }

    TAINT_NOT;
    return 0;
}

ううううううわぁ。めちゃシンプル。

OPCODE ツリーの実例

#!/usr/bin/perl

use strict;
use warnings;

my $x = 1;
my $y = 2;
my $z = $x + $y;

B::Concise （と -exec オプション）で上記のコードの OPCODE をみてみます。

% perl -MO=Concise,-exec test.pl

1  <0> enter 
2  <;> nextstate(main 3 test.pl:6) v/2
3  <$> const[IV 1] s
4  <0> padsv[$x:3,6] sRM*/LVINTRO
5  <2> sassign vKS/2
6  <;> nextstate(main 4 test.pl:7) v/2
7  <$> const[IV 2] s
8  <0> padsv[$y:4,6] sRM*/LVINTRO
9  <2> sassign vKS/2
a  <;> nextstate(main 5 test.pl:8) v/2
b  <0> padsv[$x:3,6] s
c  <0> padsv[$y:4,6] s
d  <2> add[t4] sK/2
e  <0> padsv[$z:5,6] sRM*/LVINTRO
f  <2> sassign vKS/2
g  <@> leave[1 ref] vKP/REFC

test.pl syntax OK
実行を追ってみる
1  <0> enter

ブロック（{ ... }）に入ったーよ。いつかは leave するだろう。

2  <;> nextstate(main 3 test.pl:6) v/2

次の文は test.pl の 6 行め（以下 nextstate については省略）

3  <$> const[IV 1] s

定数値「1」をスタック*4に push。

4  <0> padsv[$x:3,6] sRM*/LVINTRO

プライベート変数 $x をスタックに push（$x の値ではなく，$x という変数「ということ」を push する）。

5  <2> sassign vKS/2

スタックから2つ pop してきて，2つめ（定数 1）を1つめ（$x）にスカラー値代入する。代入結果（右辺; 定数 1）をスタックに push。

ここから飛ばすよー。

7  <$> const[IV 2] s
8  <0> padsv[$y:4,6] sRM*/LVINTRO
9  <2> sassign vKS/2

同様に $y へ定数 2 を代入する。

b  <0> padsv[$x:3,6] s
c  <0> padsv[$y:4,6] s
d  <2> add[t4] sK/2

プライベートスカラー変数 $x，$y をスタックに push。スタックから2つ pop してきて両者を add して結果を push。

ここで加算結果（3）がスタックトップにいることがミソ。

e  <0> padsv[$z:5,6] sRM*/LVINTRO
f  <2> sassign vKS/2

$z を push。スタックから2つ pop してきて，2つめ（スタックトップだった 3）を1つめ（$z）に代入。右辺（3）をスタックに push。

g  <@> leave[1 ref] vKP/REFC

ブロックおわり。

上の記述をよく読むとわかるとおり，実は代入文のたびにスタックに式の値がつまれていき消化されません。ここの rewind を nextstate でやっているのか leave でやっているのかはまだ未読です。

OPCODE ツリーの表示

んで，これじゃ人間にはわかりにくいので((せっかく，op_first や op_sibling で関連する OPCODE がつないでありますし。))，-exec オプションなしで B::Concise を実行してみます。

% perl -MO=Concise test.pl

g  <@> leave[1 ref] vKP/REFC ->(end)
1     <0> enter ->2
2     <;> nextstate(main 3 test.pl:6) v/2 ->3
5     <2> sassign vKS/2 ->6
3        <$> const[IV 1] s ->4
4        <0> padsv[$x:3,6] sRM*/LVINTRO ->5
6     <;> nextstate(main 4 test.pl:7) v/2 ->7
9     <2> sassign vKS/2 ->a
7        <$> const[IV 2] s ->8
8        <0> padsv[$y:4,6] sRM*/LVINTRO ->9
a     <;> nextstate(main 5 test.pl:8) v/2 ->b
f     <2> sassign vKS/2 ->g
d        <2> add[t4] sK/2 ->e
b           <0> padsv[$x:3,6] s ->c
c           <0> padsv[$y:4,6] s ->d
e        <0> padsv[$z:5,6] sRM*/LVINTRO ->f

test.pl syntax OK

各 OPCODE がどのように対応しているのか，どれが引数となるのか，よりわかりやすくなりましたね。


以上の話が難しく感じたのなら，スタックマシンや逆ポーランド記法について勉強してみてください。

また，暇と好奇心とC言語の知識をお持ちであれば，Lua のC拡張ライブラリを自分で書いてみることをおすすめします。シンプルな実装系ですし XS みたいに変な記法を使う必要もありません。

3種の実行時ハック

以上のことを利用した（Perl を再ビルドする必要のない）実行時ハックが存在します。

  • PL_check[] 書き換えによる OPCODE ツリー操作ハック
  • PL_ppaddr[] 書き換えハック
  • op_ppaddr 書き換えハック（via PL_check[] 書き換え）

これらのハックは構文解析後に摘要されるものなので，Shibuya.pm #9 での id:tokuhirom さんの発表にもあるとおり，構文上成立するソースに対してしか働きません。字句エラーや構文エラーがある場合，事前に怒られてしまいます。

PL_check[] 書き換えによる OPCODE ツリー操作ハック
  • 各 OPCODE type ごとに PL_check[OPCODE type] があります。
  • 対象となる OPCODE へのポインタ OP *o がわたされます。
  • 操作後の OP *o を返します。（渡された OP *o と同一でなくても構わない）
  • 構文上未解決の文法チェックやボトムレベルの最適化を行います。

つまり，ここの関数で OPCODE ツリーを変化させても構いません。Perl インタプリタにとって「想定内」です。OPCODE ツリーをコンパイルフェーズで操作できる，ということは，レキシカルに挙動を変更することができます。

逆に，コンパイルフェーズで操作しているということから，「働き方」を変えるには BEGIN フェーズで関数を呼び出す必要があります。use / no プラグマで使われる import() / unimport() を利用すると BEGIN フェーズで呼び出されるので便利です。また，OP_ENTER, OP_ENTERSUB, OP_ENTERLOOP 等スコープがかわるところに仕掛けるのもおつなものです。

  • ボトムアップパーサが（構文ルール上で）実行していくので
    • 子（kids）に関する情報はある
    • 彼自身の op_sibling はわからない（と思う）
    • 次に実行するべき OPCODE op_next はまだわからない
    • 親についても未解釈（そもそも OP 構造体に親の情報はない）

サンプルとして拙著ですが PL_check hack - daily dayflower があります。ツリーはいじってないですけどね。

PL_ppaddr[] 書き換えハック
  • 各 OPCODE type ごとに PL_ppaddr[OPCODE type] があります。
  • 登録されているのは各 OPCODE type ごとの処理関数です。

OPCODE の挙動をグローバルに変化させるので，適用範囲は……難しいですね。全 OPCODE にフックを仕掛けてプロファイリングすることもできそうですが，普通 Perl debugger interface 使う*5し。何らかの OPCODE に対するサンドボックスを実装するのもおもしろいかもしれません。

サンプルとしては Acme::NabeAtzz *6があります。シンプルなので非常にわかりやすいです。

op_ppaddr 書き換えハック
  • 各 OPCODE に op_ppaddr があります。

自作 PL_check[]() 関数において，ある OPCODE の op_ppaddr を書き換えることで，処理を override することができます。また OPCODE ごとに op_ppaddr が存在するため，コンテキスト依存に op_ppaddr を書き換えられます。たとえば，あるブロックの中だけ OPCODE の処理を変えたりフックしたりとか。

PL_check[]() で OPCODE ツリーを全部いじるより，とっつきやすいです。

実例として Shibuya.pm #9 での id:yappo さんの発表があります。コード例はプレゼン資料のほうが見やすいかも。


Shibuya.pm #9 での id:tokuhirom さんの発表にもありますが autobox という（いい意味で）crazy なモジュールがあります。これは OPCODE ツリー操作ハックと op_ppaddr 書き換えハックを利用しています。%^H まわりを無視すれば，XS コードを読み解くのは存外に難しくないです。勉強になります。

ほかの実行時ハックはないの？

いままで挙げてきたハックは先に述べたように字句的構文的に問題ないものに対してしか行えませんでした。もっと根本的に構文をいじりたいのなら，ソースフィルタである Filter::Util::Call*7 や，それをベースに使った Filter::Simple*8 を使うべきでしょう。Pure Perl で書けますので。

Inline モジュールもありますが，あれは <DATA> セクションから読み込んで共有オブジェクト生成して DynaLoader で読み込んでるだけだから，Perl の内部ハックとは言いづらいかなぁ。

参考文献

2008-07-01 追記

正直書くのも野暮な気がしますが，一応断りがきを書いておきます。

今回とりあげたハックは，（たぶん）「実用」的ではありません。Toy として Perl で遊んだり，OPCODE について深く知ったり，プライベートプロジェクトで quick hack に使ったりするぶんにはいいと思いますが。

  • そのコードは本当に PL_check 等のハックでないと実現できませんか？
    • すでに同じことをするモジュールはありませんか？
    • 通常の XS プロジェクトで実現できたり？
    • ひょっとすると Pure Perl で同じことができたり？
  • あなたが便利だと思っているそのモジュールは本当にみんなの役にたつものですか？
    • あなたのプロジェクトでは役にたつかもしれませんが，一般的な用途ですか？
  • どうしても PL_check ハックでないと実現できない場合，それはひょっとすると Perl の流儀*9と相容れないからかもしれません
    • autobox を非難するわけではありませんが，autobox はある意味 Perl の流儀から逸脱した着想から生まれたものです。
    • あなたのそのモジュールは
      • autobox のように統一感のある「世界」を提供できますか？
      • そこまでメンテナンスしていくことができますか？
      • 少なくとも「おもしろい」と誰かに思ってもらえるものですか？

萎縮させるつもりはないですが，アクロバティックなハックなので，一応，書いておきます。上から目線ですいまそん。

*1:id:yappo さん id:tokuhirom さんフォローありがとうございます。

*2:そう，Perl のパーサって YACC 生成ベースなんですね。なんとなく自作パーサかと思ってました。

*3:ほかにデバッガ版もあります。

*4:ここでいうスタックとは CPU レベルのスタックではなく，スタックマシン的な演算用データスタックです。

*5:Devel::DProf も Perl debugging API 使ってます。

*6:3が含まれる OPCODE もアホになる必要があると思うのですが……

*7:読解しようとおもったら死んだ。

*8:サラブレッド，ですよねー。

*9:流儀とかいう堅苦しい言語じゃないですが。