Vmgen ¶

3.1 Front end and VM interpreter ¶

インタープリター・ステムは通常、 入力言語をパースしてプログラムの中間表現を生成する「フロント・エンド」と、 プログラムの中間表現を実行するインタープリターに分かれます。

効率的なインタープリターの場合、 選択される中間表現は(抽象構文ツリーなどではなく、 )仮想マシン・コードです。 「仮想仮想マシン」(VM) コードは、 メモリー内に順番に配置された VM 命令で構成されます。 これらは VM インタープリターによって順番に実行されますが、 VM 分岐命令は制御フローを変更することができ、 制御構造の実装に使用されます。 実際のマシン・コードと概念的に類似しているため、 「仮想マシン」という名前が付けられます。 実機の用語に類似したさまざまな用語が使用されています。 たとえば、 「VM レジスター」(命令ポインターやスタック・ポインターなど)があり、 VM 命令は 「オペコード」と 「直接引数」(immediate arguments)で構成されます。

このフレームワークでは、 Vmgen は VM インタープリターと、 VM 命令を処理するその他のコンポーネントの構築をサポートします。 VM コード生成のサポートを除いて、 フロント・エンドのサポートはありません。 フロント・エンドは、 flex や bison などのツールでサポートされる、 従来のコンパイラー・フロント・エンド手法を使用して実装できます。

中間表現は通常、 インタープリターの内部にのみ存在しますが、 一部のシステムでは、 イメージ・ファイルとして、 または完全なリンク可能なファイル形式(JVM など)でのファイルへの保存もサポートしています。 現在、 Vmgen ではそのような機能に対する特別なサポートはありませんが、 命令記述に記載されている情報が役に立つ可能性があります。 また、 私達は機能のリクエストや提案をお待ちしています。

3.2 Data handling ¶

ほとんどの VM は、 VM 命令間で一時データを渡すために 1 つ以上のスタックを使用します。 私達は、 通常、 スタック・アーキテクチャを使用する方が簡単かつ高速であると考えていますが、 もう一つのオプションとして、 仮想マシンにレジスター・マシン・アーキテクチャを使用することが考えられます。

ただし、 このオプションはスタック・マシン・アーキテクチャよりも実装に時間がかかるか、 非常に複雑です。

Vmgen にはスタック VM に対する特別なサポートと最適化があり、 スタック VM の実装が簡単かつ効率的に行えます。

また、 Vmgen (see Register Machines) を使用して レジスター VM を実装することもできます。 その場合でも、 あなたは Vmgen のほとんどの機能を活用できます。

スタック項目はすべて同一サイズなので、 通常は整数やポインターや浮動小数点数値は同じサイズ幅になります。 Vmgen は、 2 つの連続したスタック項目を単一の値として扱うことをサポートしていますが、 それより大きいものは、 スタックに置いた、 データへのポインターを使用して、 他のメモリ領域(ヒープなど)に保持するのが最適です。

もう 1 つのデータ源は、 (VM 命令ストリーム内の) 即時引数 VM 命令達(immediate arguments VM instructions)です。 VM 命令ストリームは、 Vmgen のスタックと同様に処理されます。

Vmgen には、 「ガーベジ・コレクション」に対するサポートも制限も組み込まれていません。 ガベージ・コレクションが必要な場合は、 ランタイム・ライブラリーでそれを提供する必要があります。 「参照カウント」(reference counting)を使用するのはおそらく困難、 可能な場合もあります(興味がある場合は私達にお問い合わせください)。

3.3 Dispatch ¶

Vmgen を使用する場合、 このセクションを理解する必要はおそらくありませんが、 役立つ場合もあります。 ここでスキップして、 あとでディスパッチ方法に関する記述がわかりにくい場合にこのセクションを読むといいでしょう。

1 つの VM 命令を実行した後、 VM インタープリターは次の VM 命令にディスパッチ(dispatch;切り替え作業)する必要があります(Vmgen はディスパッチ・ルーチン「NEXT」を呼び出します)。 Vmgen は 2 つのディスパッチ方法をサポートしています:

switch dispatch ¶

この方法では、 VM インタープリターに巨大な switch ステートメントが含まれており、 VM 命令ごとに 1 つの case があります。 VM 命令のオペコードは、 VM コード内の整数(enum によって生成されるなどする)によって表され、 ディスパッチは、 次のオペコードをロードし、 switch して、 適切な case で続行することによって行います。 VM 命令の実行後、 VM インタープリタはディスパッチ・コードに戻ります。

threaded code ¶

このメソッドは、 VM 命令を実行するためのマシン・コード断片の開始アドレスによって VM 命令オペコードを表します。 ディスパッチ(切り替え作業)は、 このアドレスのロードと、 そこへのジャンプと VM 命令ポインターのインクリメントで構成されます。 通常、 スレッド化コードのディスパッチ・コードは、 VM 命令を実行するコードに直接追加されます。 スレッド化コードは ANSI C では実装できませんが、 GNU C の label-as-values 拡張機能を使用して実装できます(see Labels as Values in GNU C Manual)。

インタープリターやベンチマークやマシンによっては、 スレッド化コードはスイッチ・ディスパッチより 2 倍早くなることがあります。

5.1 Example overview ¶

Vmgen を使用する同一の例として、 vmgen-ex と vmgen-ex2 の 2 つのバージョンがあります(例として Gforth もありますが、 追加の(文書化されていない)機能が使用されており、 他のいくつかの点でも異なります)。 この例では、 JavaVM のような小さな仮想マシンを備えた小さな Modula-2 のような言語である「mini」言語を実装しています。

2つの例の違いは、 vmgen-ex は多くのキャスト(cast)を使用するのに対し、 vmgen-ex2 はほとんどのキャストを回避し、 代わりに共用体(unions)を使用することです。 このマニュアルの残りの部分では、 通常、 vmgen-ex 内のファイルについてのみ言及します。 共用体(union)を使用したい場合は、 vmgen-ex2 内の同等のファイルを使用してください。

各例で提供されるファイルは以下のとおりです:

Makefile
README
disasm.c           wrapper file
engine.c           wrapper file
peephole.c         wrapper file
profile.c          wrapper file
mini-inst.vmg      simple VM instructions
mini-super.vmg     superinstructions (empty at first)
mini.h             common declarations
mini.l             scanner
mini.y             front end (parser, VM code generator)
support.c          main() and other support functions
fib.mini           example mini program
simple.mini        example mini program
test.mini          example mini program (tests everything)
test.out           test.mini output
stat.awk           プロファイル情報を集約するためのスクリプト
peephole-blacklist スーパー命令で許可されない命令のリスト
seq2rule.awk       スーパー命令を生成するためのスクリプト

あなた独自のインタープリターを作る場合、 通常、 以下のファイル群はコピーして使い、 変更することはほとんどないでしょう:

disasm.c           wrapper file
engine.c           wrapper file
peephole.c         wrapper file
profile.c          wrapper file
stat.awk           プロファイル情報を集約するためのスクリプト
seq2rule.awk       スーパー命令を生成するためのスクリプト

そして、 通常、 あなたは、 以下のファイル群を大幅に変更するか、 置き換える事になります:

Makefile
mini-inst.vmg      simple VM instructions
mini.h             common declarations
mini.l             scanner
mini.y             front end (parser, VM code generator)
support.c          main() and other support functions
peephole-blacklist スーパー命令で許可されない命令のリスト

example のディレクトリに cd してから make と入力すると、 example をビルドできます。 make check で動作することを確認できます。 以下のようにして mini 言語のプログラムを実行できます:

./mini fib.mini

オプションについて詳しくは、 ./mini -h と入力してください。

5.2 Using profiling to create superinstructions ¶

作者は Makefile には、 プロファイリングを使用してスーパー命令を作成するためのルールを追加していません(スーパー命令選択の選択肢はたくさんありますが、 それらの選択肢を Makefile にハードコードしたくありませんでした)が、 サポートするスクリプトがいくつかあります。 例:

fib.mini と test.mini をトレーニング・プログラムとして使用すると、 以下のようなプロファイルが得られます:

make fib.prof test.prof #数秒かかります

これらのプロファイルは stat.awk で集約できます:

awk -f stat.awk fib.prof test.prof

結果には以下のような行が含まれます:

      2      16        36910041 loadlocal lit

これは、 シーケンス loadlocal lit が 2 つのプロファイルで合計 16 回静的に発生し、 動的実行数が 36910041 であることを意味します。

数値はスーパー命令を選択するためにさまざまな方法で使用できます。 たとえば、 動的実行数が 10000 を超えるシーケンスをすべて選択したい場合は、 以下のパイプラインを使用します:

awk -f stat.awk fib.prof test.prof|
awk '$3>=10000'|                #シーケンスを選択
fgrep -v -f peephole-blacklist| #良くない命令を排除
awk -f seq2rule.awk|  #シーケンスをスーパー命令ルールに変換
sort -k 3 >mini-super.vmg       #シーケンスを並べ替え

ファイル peephole-blacklist には、スタックまたはスタック・ポインター(mini 言語の場合: call 、return)に直接アクセスするすべての命令が含まれています。 並べ替え手順は、 プレフィックスが、 大きなスーパー命令よりも前に配置されるようにするために必要です。

いまや、 あなたは ‘make’ と言うだけでスーパー命令を備えたバージョンの mini 言語を作成できるようになりました。

6.1 Input File Grammar ¶

文法は EBNF 形式で、 a|b は「a または b」、 {c} は c の 0 回以上の繰り返しを意味し、 [d] は d の 0 回または 1 回の繰り返しを意味します。

Vmgen の入力は自由書式ではないため、 改行(および場合によっては空白)をどこに入れるかに注意する必要があります。

description: {instruction|comment|eval-escape|c-escape}

instruction: simple-inst|superinst

simple-inst: ident '(' stack-effect ')' newline c-code newline newline

stack-effect: {ident} '--' {ident}

super-inst: ident '=' ident {ident}  

comment:      '\ '  text newline

eval-escape:  '\E ' text newline

c-escape:     '\C ' text newline

注意: この文法の \ は、 印刷不可能な文字の C 言語スタイルのエンコーディングではなく、 文字通りの意味であることに注意してください。

simple-inst で C 言語コードを区切る(delimit)方法は 2 つあります:

• 行頭が ‘{’ で始まる場合(つまり、 その前に空白も無い場合)、 (改行に続いて)行頭の ‘}’ で終了する必要があります。 この場合、 C 言語コード内に空行が含まれる可能性があります(通常、 変数定義とステートメントの間で使用されます)。
• ‘{’ で始めない場合。 この場合、 C 言語コードは最初の空行で終了するため、 このコード内に空行を含めることはできません。

comment と eval-escape と c-escape 内の text には改行を含めることはできません。 Ide​​nt は、 C 言語識別子の通常の規則に準拠する必要があります(そうしないと、 Vmgen 出力で C 言語のコンパイラーが詰まり(choke)ます)。 Ide​​nt は、 stack-effect の ident にスタック・プレフィックス(スタック・プレフィックス構文については see Eval escapes 参照)が付いている場合がある点を除き、 C 言語識別子の通常の規則に準拠する必要があります。

c-escape は text を各出力ファイルに渡します(‘\C’ 無しで)。 これは主に条件付きコンパイルに役立ちます(つまり、 ‘\C #if ...’ などを記述します)。

文法で指定された構文に加えて、 Vmgen は ‘m4 -s’ (see Invoking m4 in GNU m4)や、 同様のツールによって生成された同期行(sync lines)(‘#line’ で始まる行)も処理します。 これにより、 C 言語コンパイラーのエラー・メッセージを C 言語コードの元のソースに関連付けることができます。

Vmgen は、 ここで説明した文法を超えたいくつかの拡張機能を理解しますが、 これらの拡張機能は Gforth を構築する場合にのみ役立ちます。 Gforth に使用される書式の説明は prim にあります。

text: stack-decl|type-prefix-decl|stack-prefix-decl|set-flag

stack-decl: 'stack ' ident ident ident
type-prefix-decl: 
    's" ' string '" ' ('single'|'double') ident 'type-prefix' ident
stack-prefix-decl:  ident 'stack-prefix' string
set-flag: ('store-optimization'|'include-skipped-insts') ('on'|'off')

stack                 ( "name" "pointer" "type" -- )
                      ( name execution: -- stack )
type-prefix           ( addr u item-size stack "prefix" -- )
single                ( -- item-size )
double                ( -- item-size )
stack-prefix          ( stack "prefix" -- )
store-optimization    ( -- addr )
include-skipped-insts ( -- addr )

6.2 Simple instructions ¶

例として、 以下の簡単な VM 命令の記述を使用します:

sub ( i1 i2 -- i )
i = i1-i2;

最初の行には、 VM 命令の名前 (sub) とそのスタック効果 (i1 i2 -- i) を指定します。 最初の行以外の記述の残りの部分は単なる C 言語コードです。

スタック効果では、 sub がデータ・スタックから 2 つの整数を取得し、 それらを C 言語の変数 i1 と i2 に格納することを指定します(右端の項目 (i2) が、 スタックのトップです: i1 をスタックにプッシュし、 次に i2 をスタックにプッシュすると、 結果のスタック状態は i1 i2 になります)。 そしてその後、 その後 1 つの整数 (i) をスタックにプッシュします(右端の項目がスタックの一番上になります)。

スタック項目の型とスタックを知るにはどうすればよいでしょうか? Vmgen は、 Fortran と同様にプレフィックスを使用します。 Fortran とは対照的に、 あなたは最初にプレフィックスを定義する必要があります:

\E s" Cell"   single data-stack type-prefix i

これは、 型 Cell (mini.h では long として定義)を参照するプレフィックス i を定義し、 デフォルトでは data-stack を参照します。 また、 この型が 1 つのスタック項目(single)を占めることも指定します。 型プレフィックスは変数名の一部です。

data-stack を使用する前に、 この方法で data-stack を定義する必要があります:

\E stack data-stack sp Cell

この行は、 スタック・ポインター sp を使用するスタック data-stack を定義し、 各項目の基本タイプは Cell です。 他の型は 1 つまたは 2 つの Cell に収まる必要があり(型の幅が single か double かによって異なります)、 型キャスト・マクロ(see VM engine)を使用して data-stack にアクセスするときに Cell との間でキャストされます。 Vmgen 製インタープリターではスタックは、 デフォルトでは、 より低いアドレスに向かって伸長します(see Stack growth direction)。

スタック・プレフィックスを使用して、 スタック項目のデフォルト・スタックをオーバーライドできます。 たとえば、 以下の命令について考えてみましょう:

lit ( #i -- i )

VM 命令 lit は、 命令ストリームから(プレフィックス # で示される) 項目 i を取得し、 それを(デフォルトの)データ・スタックにプッシュします。 スタック・プレフィックスは変数名の一部ではありません。 スタック・プレフィックスは以下のように定義されています:

\E inst-stream stack-prefix #
\E data-stack  stack-prefix S:

この定義は、 スタック・プレフィックス # が「スタック inst-stream 」を指定することを定義します。 命令ストリーム(inst-stream)は通常のスタックとは振る舞いが少し異なるため、 事前に定義済であり、 あなたが定義する必要はありません。

命令ストリームには命令とその直接引数(immediate arguments)が含まれるため、 引数が命令ストリームからのものであることを指定することは、 直接引数であることを示しています。 もちろん、 命令ストリーム引数は、 スタック効果の -- の左側にのみ出現できます。 複数の命令ストリーム引数がある場合、 (あなたの直観どおり)左端が最初の引数になります。

return ( #iadjust S:... target afp i1 -- i2 )
SET_IP(target);
sp = (Cell *)(((char *)sp)+iadjust);
fp = afp;
i2=i1;

\E : sp-access-transform ( itemnum -- index ) negate 1- ;
\E ' sp-access-transform ' data-stack >body stack-access-transform !

6.3 Superinstructions ¶

注意: (静的な)スーパー命令(superinstructions)にあまり多くの作業を費やさないでください。 Vmgen の将来のバージョンでは、 動的スーパー命令がサポートされる予定で(Ian Piumarta and Fabio Riccardi, Optimizing Direct Threaded Code by Selective Inlining, PLDI’98 参照)、 静的スーパー命令の利点ははるかに少なくなっています(暫定的な結果は、 係数 1.1 の高速化)。

以下にスーパー命令(superinstruction)定義の例を示します:

lit_sub = lit sub

lit_sub はスーパー命令(superinstruction)の名前で、 lit と sub はそのコンポーネントです。 このスーパー命令は、 シーケンス「lit sub」と同じアクションを実行します。 これは、 そのシーケンスが発生するたびに VM コード生成関数によって自動的に生成されるため、 このスーパー命令を使用したい場合は、 この定義を追加するだけで済みます(see VM profiler により部分的に自動化することもできます)。

Vmgen では、コンポーネントの命令群が、 コンポーネントを使用するスーパー命令(superinstructions)より前に定義された単純な命令(simple instructions)であることが必要です。 現在、 Vmgen では、 スーパー命令の先頭にあるすべてのサブ・シーケンス(プレフィックス)が当該スーパー命令より前にスーパー命令として定義されている必要もあります。 つまり、 スーパー命令を定義したい場合

foo4 = load add sub mul

あなたは、 まず、 load と add と sub と mul を定義する必要があります。 さらに

foo2 = load add
foo3 = load add sub

ここで、 sumof4 は sumof5 の最長のプレフィックスで、 sumof3 は sumof4 の最長のプレフィックスです。 (訳注: 推敲途中だったかな？ 意味不明)

注意: Vmgen は、 生成するコードのみがスタック・ポインターや、 命令ポインターや、 さまざまなスタック項目にアクセスすると想定しており、 この想定に基づいて最適化を実行することに注意してください。 したがって、 C 言語コードで命令ポインターを変更する VM 命令は、 最後のコンポーネントとしてのみ使用する必要があります。 C 言語コードがスタック・ポインターにアクセスする VM 命令は、 コンポーネントとしてまったく使用しないでください。 Vmgen はこれらの制限をチェックsせず、 インタープリターでバグが発生するだけです。

Vmgen フラグ include-skipped-insts は、 スーパー命令(superinstruction)コードの生成に影響します。 現在、 のぞき穴最適化(peephole optimizer)では両方のバリエーションはサポートされていないため、 このフラグは今のところそのままにしておきます。

6.4 Store Optimization ¶

格納最適化(store optimization)というマイナーな最適化(Gforth の実行命令の 0.6% ～ 0.8% 削減)では、 命令の記述に追加の要件が課されるため、 デフォルトでは無効になっています。

これはは何をするのでしょうか？ 以下のような命令を考えてみましょう

dup ( n -- n n )

簡単にするために、 スタックのトップをレジスタにキャッシュしていないことも仮定します。 今、 dup の C 言語コードは、 最初に n をスタックからロードし、 次にそれをスタックに 2 回 格納し、 そのうち 1 回は元のアドレスに格納します。 元のアドレスに格納する回は不要ですが、 gcc はそれを最適化しないので、 代わりに vmgen がそれを行うことができます(格納最適化(store optimization)をオンにしている場合)。

Vmgen は、 スタック項目の名前を使用して、 スタック項目に開始時と同一の値が含まれているかを決めます。 したがって、 格納最適化を使用する場合は、 入力と出力で同じ名前を持つスタック項目も同じ値を持ち、 提供する C 言語コードで変更されないことを確認する必要があります。 つまり、 格納最適化をオンにすると、 以下のコードは失敗する可能性があります:

add1 ( n -- n )
n++;

代わりに、 あなたは別の名前を使用する必要があります。 つまり以下のようにします:

add1 ( n1 -- n2 )
n2=n1+1;

同様に、 格納最適化では、 スタック・ポインターが Vmgen で生成されたコードによってのみ変更されることを前提としています。 C 言語コードでスタック・ポインターを変更する場合は、 入力スタック項目と出力スタック項目に異なる名前を使用して(おそらく間違った)格納最適化を回避するか、 この VM 命令の格納最適化をオフにしてください。

格納最適化を有効にするには、 以下のように記述します

\E store-optimization on

これをファイルの先頭に記述します。 任意の 2 つの VM 命令記述の間で、 この最適化をオンまたはオフにできます。 再度オフにするには、 以下を使用できます。

\E store-optimization off

6.5 Register Machines ¶

Vmgen を使用してスタック VM ではなくレジスター VM を実装する場合は、 直接実行する方法とスーパー命令を使用する方法の 2 つがあります。

直接的な方法を使用する場合は、 以下のように、 レジスタ番号を直接の引数として受け取る命令を定義します:

add3 ( #src1 #src2 #dest -- )
reg[dest] = reg[src1]+reg[src2];

この方法の欠点は、 トレース中にレジスター番号のみが表示され、 レジスタの内容は表示されないことです。 実際には、 printarg_src (see VM engine)を適切に定義すると、 開始時にソース・レジスターの値を出力できますが、 終了時に宛先レジスターの値を出力することはできません。

スーパー命令(superinstructions)を使用してレジスター VM を定義する場合は、 以下のように、 スタックを使用する単純な命令(simple instructions)を定義してから、 全体的なスタック効果のないスーパー命令を定義します:

loadreg ( #src -- n )
n = reg[src];

storereg ( n #dest -- )
reg[dest] = n;

adds ( n1 n2 -- n )
n = n1+n2;

add3 = loadreg loadreg adds storereg

この方法の利点は、 トレース中にレジスター番号だけでなく値も表示されることです。 この方法の欠点は、 現時点ではスーパー命令(superinstructions)を直接生成できず、 単純な命令(simple instructions)のシーケンスを生成することによってのみ生成できることです(需要があれば、 作者達は将来これを変更するかもしれません)。

上記の問題とは別に、 レジスター VM のサポートを改善可能でしょうか？ VM インタープリターに関連して「レジスター・マシン」という用語を使用する場合、 人によって意味が異なるため、 一般的な方法でこれを行う方法を理解するのは困難です。 ただし、 その方向でアイデアや要望がある場合は、 著者にお知らせください(see Contact)。

8.1 VM engine ¶

VM エンジンは、 VM コードを実行するための VM インタープリターです。 それはインタープリター的システムにとって不可欠なものです。

Vmgen は、 VM 命令ディスパッチ(dispatch;切り替え作業)の 2 つの方法をサポートしています。 「スレッド化コード」(高速ですが gcc 固有)と、 「スイッチ・ディスパッチ」(低速ですが、 C 言語コンパイラ間で移植可能)です。 条件付きコンパイル(‘defined(__GNUC__)’)を使用してこれらの方法を選択でき、 著者達の例ではそうしています。

どちらの方法でも、 VM エンジンは C 言語レベルの関数に含まれています。 Vmgen は関数の内容のほとんどを生成しますが、 この関数の定義と、エンジンで使用されるマクロと変数の定義と、 変数の初期化を行う必要があります。 私達の例では、 エンジン関数には name-labels.i も含まれています(see VM instruction table)。

コードの実行に加えて、 VM エンジンはオプションで、 実行された命令や、 実行された命令の引数や、 実行された命令の結果のトレースを出力することもできます。 スーパー命令(superinstructions)の場合は、 コンポーネント命令のみが実行されたかのようにトレースを出力します。 これにより、 古いスーパー命令と比較可能なトレースを維持しながら、 新しいスーパー命令を導入することができます(これは デグレ・チェック(regression tests)のために重要です)。

トレース・コードを出力するかどうかを各命令でチェックするとパフォーマンスが大幅に低下するため、 エンジンのコピーを 2 つ作成することをお勧めします。 1 つは高速実行用、 もう 1 つはトレース用です。 例については、 vmgen-ex/Makefile の engine.o と engine-debug.o の makeルールを参照してください。

以下のマクロと変数が name-vm.i で使用されます:

LABEL(inst_name) ¶

これは、 ジャンプまたは switch ラベルを提供するために各 VM 命令の直前で使用されます(‘:’ は Vmgen によって提供されます)。 スイッチ・ディスパッチの場合、 これは ‘case label:’ に展開されるべきです。 スレッド化コード・ディスパッチの場合は、 これを ‘label:’ に展開するだけです。 どちらの場合も、 label は通常、 名前の競合を避けるために何らかのプレフィックスまたはサフィックスを付けた inst_name です。

LABEL2(inst_name) ¶

これは動的スーパー命令(dynamic superinstructions)に使用されます。 現時点では、 これは「無」(nothing)に展開されるべきです。

NAME(inst_name_string) ¶

VM 命令の名前をパラメーターとして含む文字列を含む VM 命令を入力すると呼び出されます。 通常の実行では、 これは「無」(nothing)に展開されるはずですが、 トレースの場合は通常、 名前と、 場合によってはその他の情報(この例ではいくつかの VM レジスター)が出力されます。

DEF_CA ¶

通常は空(empty)です。 VM 命令の開始時に新しいスコープ内で呼び出されます。 すべての VM 命令中に表示される変数を定義するために使用できます。 このマクロを空ではないものとして定義する場合は、 マクロ定義は ‘;’ で終了させる必要があります。

NEXT_P0 NEXT_P1 NEXT_P2 ¶

命令ディスパッチ用の 3 つの部品。 さまざまなプロセッサで最高のパフォーマンスを得るために、 さまざまな方法で定義できます(例の engine.c または Gforth の engine/threaded.h を参照)。 ‘NEXT_P0’ は VM 命令の開始直後(ただし ‘DEF_CA’ の後)、 ‘NEXT_P1’ はユーザー指定の C 言語コードの直後、 そして ‘NEXT_P2’ は最後に呼び出されます。 実際のジャンプは ‘NEXT_P2’ によって実行する必要があります(これを実行するのが早すぎると、 VM 命令の重要な部分が実行されなくなります)。

バリエーションの最も単純なモノは、 ‘NEXT_P2’ がすべてを行い、 他のマクロは何も実行しないヤツです。 ‘IP’ や ‘SET_IP’ や ‘IP’ や ‘INC_IP’ や ‘IPTOS’ などの関連マクロも非常に簡単に定義できます。 スイッチ・ディスパッチの場合、 このコードはディスパッチ・コード(この例では ‘goto next_inst;’) へのジャンプだけで構成されます。 直接スレッド化コード(direct threaded code)の場合は、 ‘({cfa=*ip++; goto *cfa;})’ のようなもので構成されます。

コード(普通は ‘cfa=*ip++;’ というコード)を ‘NEXT_P1’ にセットすることは通常問題を引き起こしませんが、 ‘NEXT_P0’ にコードをセットすると、 通常、他のマクロも変更する必要があります(そして、 少なくとも Alpha 版の Gforth については、 コンパイラーは関連するものを自動的にスケジュール設定することが多いため、 それほど大きな価値はありません)。 さらに極端なバリエーションとしては、 コードをさらに離れた、 たとえば前の VM 命令の NEXT_P1 にセットすることです (プリフェッチ。 PowerPC で便利です)。

INC_IP(n) ¶

IP に n を足しこみます。

SET_IP(target) ¶

IP に target をセットします。

vm_A2B(a,b) ¶

(A 型の) ‘a’ を (B 型の) ‘b’ に割り当てる型キャスト・マクロ。 これは主に、 スタック項目を変数に入れたりスタック項目から変数へ戻したりするために使用されます。 したがって、 スタックの基本型(この例では Cell)と、 そのスタックで使用される型プレフィックス形式(スタック項目を変数に入れる方向とスタック項目から変数へ戻す方向)すべての組み合わせに対してマクロを定義する必要があります。 型プレフィックス形式の場合は、 (C言語の型名ではない)型プレフィックスを型名(‘vm_Cell2Cell’ ではなく ‘vm_Cell2i’)として使用します。 さらに、 スタックの基本型 X に対して(スーパー命令で使われる) vm_X2X マクロを定義する必要があります。

事前定義された ‘inst-stream’ (命令ストリーム)のスタック基本型は ‘Cell’ です。 同一項目サイズのスタックが必要な場合、 その基本型を ‘Cell’ にすると、 通常、 定義する必要があるマクロの数が減ります。

ただし、 私達の例では大きく異なります: vmgen-ex はこれらのマクロでキャストを使用しますが、 vmgen-ex2 は共用体(union)フィールドの選択(または共用体フィールドへの代入)を使用します。 浮動小数点数(floats)を整数にキャストしたり、 その逆を行うとビット・パターンが変更されることに注意してください(そして、 これはあなたが望む事ではありません)。 この場合の選択肢は、 (一時的な(temporary))共用体を使用するか、 値のアドレスを取得してポインタをキャストし、 それを逆参照(dereference)することです(常に可能であるとは限らず、 しばしばコストがかさみます)。

vm_twoA2B(a1,a2,b) ¶

vm_B2twoA(b,a1,a2)

2 つのスタック項目(a1、a2)と 2 つのスタック項目を取る型の変数 b の間の型キャスト。 これは私達の小さな例では発生しませんが、 例として Gforth を参照してください(engine/forth.h の vm_twoCell2d を参照してください)。

stackpointer ¶

使用されるスタックごとに、 スタック宣言で指定されたスタック・ポインター名が使用されます。 通常のスタックの場合、 これは左辺値に解決される式(l-expression)でなければなりません。 通常、 これはスタックの基本型へのポインタとして宣言された変数です。 ‘inst-stream’ (命令ストリーム)の場合、 名前は ‘IP’ で、 プレーンな右辺値を指定できます。 通常、 これは NEXT_P* のさまざまな実装間の違いを抽象化するマクロです。

IMM_ARG(access,value) ¶

これを "(access)" に展開するように定義します。 これは将来の拡張機能のための単なるプレースホルダーです。

stackpointerTOS ¶

stackpointer が指し示すスタックのTOS(スタックのトップ)。 そのスタックに対してスタックのトップ・キャッシュを使用している場合は、 これを変数として定義する必要があります。 そのスタックがスタックのトップ・キャッシュを使用していない場合、 これは ‘stackpointer[0]’ に展開されるマクロである必要があります。 事前定義された ‘inst-stream’ (命令ストリーム)のスタック・ポインターは ‘IP’ と呼ばれるため、 TOS(スタックの最上位)は ‘IPTOS’ と呼ばれます。

IF_stackpointerTOS(expr) ¶

stackpointer が指し示すスタックにスタックのトップ・キャッシュが使用されている場合に、 expr を実行するためのマクロ。 つまり、 stackpointer のスタックのトップ・キャッシュがある場合に expr を実行する必要があります。 それ以外の場合は何もしません。

SUPER_END ¶

これは VM プロファイラー(see VM profiler)によって使用されます。 通常の操作では何も行わないので、 プロファイリングのためには vm_count_block(IP) を呼び出す必要があります。

SUPER_CONTINUE ¶

これは Vmgen への単なるヒントであり、 C 言語レベルでは何も行いません。

MAYBE_UNUSED ¶

gcc-2.7 以降では、 これを __attribute__((unused)) として定義する必要があります。 スーパー命令(superinstructions)のコード内の未使用の変数に関する警告が抑制されます。 これを定義する必要があるのは、 あなたがスーパー命令を使用している場合のみです。

VM_DEBUG ¶

これが定義されている場合、 トレース・コードがコンパイルされます(解釈(interpretation)は遅くなりますが、 デバッグは向上します)。 私達の例では、 エンジンの 2 つのバージョンをコンパイルします: 1 つはトレースできない高速実行バージョンで、 もう 1 つはトレースとプロファイリングが可能です。

vm_debug ¶

‘VM_DEBUG’ が定義されている場合にのみ必要です。 この変数に true が含まれている場合、 VM 命令はトレース出力を生成します。 いつでもオンまたはオフにできます。

vm_out ¶

‘VM_DEBUG’ が定義されている場合にのみ必要です。 トレース出力を印刷するファイルを指定します(‘FILE *’ とタイプします)。

printarg_type(value) ¶

‘VM_DEBUG’ が定義されている場合にのみ必要です。 type に適した方法で value を出力するためのマクロまたは関数です。 これは、 トレース中にスタック項目の値を出力するために使用されます。 Type は通常、type-prefix 定義で指定された型プレフィックスです(例: ‘printarg_i’)。 スーパー命令(superinstructions)では、 これは現在のスタックの基本タイプです。

8.2 VM instruction table ¶

スレッド化コードの場合は、 すべての VM 命令のラベルを含んだテーブルを作成する必要もあります。 これは VM コード生成(see VM code generation)に必要であり、 ラベルは外部から見えないため、 エンジン関数内で実行する必要があります。 次に、 VM コード生成関数で使用できるように、 関数の外に渡す(そして ‘vm_prim’ に割り当てする)必要があります。

これは、 VM 命令テーブルを生成するために最初にエンジン関数を呼び出す必要があり、 その後 VM コードを生成した後、 生成された VM コードを実行するためにエンジン関数を再度呼び出す必要があることを意味します(はい、これは醜いです)。 我々のプログラム例では、 エンジン関数を呼び出すこれら 2 つのモードは、 パラメーター ip0 の値によって区別されます(0 に等しい場合はテーブルが渡され、 それ以外の場合は VM コードが実行されます)。 我々の例では、 テーブルを ‘vm_prim’ に割り当て、 それを ‘engine’ から返すことによってテーブルを渡します。

我々の例 (vmgen-ex/engine.c) では、スイッチ・ディスパッチ用のテーブルも構築します。 これは主に均一性を目的として行われます。

スイッチ・ディスパッチの場合、 enum で case ラベルとして使用される VM 命令オペコードも定義する必要があります。

両方の目的 (VM 命令テーブルと enum )のために、 ファイル name-labels.i が Vmgen によって生成されます。 あなたはこのファイルで使用される以下のマクロを定義する必要があります:

INST_ADDR(inst_name) ¶

スイッチ・ディスパッチの場合、 これは name-labels.i のどちらの使用法でもスイッチ・ラベルの名前にすぎません(‘LABEL(inst_name)’ で使用されているのと同一の名前です)。 スレッド化コード・ディスパッチの場合、 これは ‘LABEL(inst_name)’ で定義されたラベルのアドレスです。 アドレスは ‘&&’ で取得されます(see Labels as Values in GNU C Manual)。

8.3 VM code generation ¶

Vmgen は、フロント・エンドが VM コードを生成するために呼び出すことができる VM コード生成関数を name-gen.i に生成します。 これはインタープリター・システム(interpretive system)には不可欠なものです。

VM 命令 ‘x ( #a b #c -- d )’ の場合、 Vmgen は以下のプロトタイプを持つ関数を生成します

void gen_x(Inst **ctp, a_type a, c_type c)

ctp 引数は、 次の命令へのポインターを指します。 *ctp は生成関数によって増加されます。 つまり、 あなたは生成するコード用のメモリを事前に割り当て、 このメモリ領域の先頭に *ctp を設定して開始する必要があります。 メモリが不足する前に、 新しい領域を割り当て、 新しい領域への VM レベルのジャンプを生成します(このオーバーフロー処理は我々の例では実装されていません)。

他の引数は、 VM 命令の直接引数(immediate arguments)に対応します(type_prefix 宣言で定義されている適切な型を使用します)。

以下の型や変数や関数が name-gen.i で使用されます:

Inst ¶

VM 命令のタイプ。 スレッド化コードを使用する場合、 これは void * です。 スイッチ・ディスパッチの場合、 これは整数型です。

vm_prim ¶

VM 命令テーブル (タイプ: Inst * 。 see VM instruction table)。

gen_inst(Inst **ctp, Inst i) ¶

この関数は命令 i をコンパイルします。 vmgen-ex/peephole.c をご覧ください。 スーパー命令(superinstructions)を使用したくない場合(関数例の最後の 2 行のみの場合)は簡単ですが、 この例ではスーパー命令を使用可能なため、 少し複雑になります(see Peephole optimization)。

genarg_type_prefix(Inst **ctp, type type_prefix) ¶

これにより、 (type-prefix 定義で定義されている) type の直接引数(immediate argument)がコンパイルされます。 これらの関数を定義するのは簡単です(vmgen-ex/support.c を参照)。 あなたが直接引数(immediate argument)として使用するタイプごとに、 これらの関数のいずれかが必要です。

これらの関数を使用してコードを生成することに加えて、 スーパー命令(superinstructions)を使用したい場合は(または、 Vmgen でサポートされているプロファイリングを使用したい場合は; ただし、 このサポートは主にスーパー命令の選択にも役立ちます)は、 すべての基本ブロック・エントリ・ポイントで BB_BOUNDARY を呼び出す必要があります。 あなたが BB_BOUNDARY を利用する場合、 あなたは BB_BOUNDARY も定義する必要があります(vmgen-ex/mini.y の定義をご覧ください)。

分岐の後に BB_BOUNDARY を呼び出す必要はありません。 なぜなら、 あなたは途中に分岐を含むスーパー命令を定義することはないでしょう(もしあなたがそうして、 それがうまくいくなら、 分岐でスーパー命令で終了する理由はありません)、 そして、 分岐はプロファイラに自分自身をアナウンスするからです。

8.4 Peephole optimization ¶

あなたがスーパー命令(superinstructions)を使用する場合にのみ、 のぞき穴最適化(peephole optimization)が必要です。 ただし、 スーパー命令を使用しない場合に、 のぞき穴最適化のコードを持っていても、 それほど差し障りはありません。

スーパー命令(superinstruction)の選択には、 単純な貪欲な覗き穴最適化(simple greedy peephole optimization)アルゴリズムが使用されます: gen_inst が VM 命令をコンパイルするたびに、 それを直前の VM 命令と結合(combine)できるかどうかがチェックされます(これは、以前ののぞき穴最適化から生じたスーパー命令である可能性もあります)。 結合できる場合、 現在の ‘*ctp’ に i を配置する代わりに、 最後の命令を結合された命令に変更します。

のぞき穴最適化のコードは vmgen-ex/peephole.c にあります。 このファイルはほぼそのまま使用できます。 Vmgen は、 除き穴最適化のデータを含む file-peephole.i を生成します。

あなたは、 ‘vm_prim’ を初期化した後、 VM コードをコンパイルして覗き穴最適化のためのデータ構造を初期化する前に、 ‘init_peeptable()’ を呼び出す必要があります。 その後、 VM コード生成関数を使用してコンパイルすると、 VM 命令がスーパー命令(superinstructions)に自動的に結合されます。 あなたが VM 分岐ターゲット間で命令を結合したくない時(そうしないと、 分岐先の適切な VM 命令が存在しなくなります)、 分岐ターゲットで BB_BOUNDARY (see VM code generation) を呼び出す必要があります。

8.5 VM disassembler ¶

VM コード逆アセンブラはインタープリター・システムではオプションですが、 フロント・エンドでのバグの検出(および VM インタープリターのバグと区別するため)に非常に役立つため、 開発およびメンテナンス中は強く推奨します。

Vmgen は、 file-disasm.i を生成することで VM コードの逆アセンブルをサポートします。 vmgen-ex/disasm.c と同様に、 このコードを関数にラップする必要があります。 このファイルはほぼそのまま使用できます。 ‘vm_A2B(a,b)’ や ‘vm_out’ や ‘printarg_type(value)’ に加えて、 上記で説明したように、 以下のマクロと変数が file-disasm.i で使用されます(あなたはこれらを定義する必要があります):

ip

この変数は、 現在の VM 命令のオペコードを指します。

IP IPTOS ¶

‘IPTOS’ は現在の VM 命令の最初の引数であり、 ‘IP’ はそれを指します。 これはエンジンとまったく同じですが、 ここで ‘ip’ は VM 命令のオペコードを指します(エンジンとは対照的に、 ‘ip’ は次のセル、 またはさらにその 1 つ先のセルを指します)。

VM_IS_INST(Inst i, int n) ¶

オペコード ‘i’ が VM 命令テーブルの ‘n’ 番目のエントリと同じかどうかをテストします。

8.6 VM profiler ¶

VM プロファイラーは、 VM 命令シーケンスの実行カウントと出現カウントを取得するように設計されており、 これらのカウントはスーパー命令(superinstructions)としてシーケンスを選択するために使用できます。 VM プロファイラーは、 おそらくインタプリタ・システム(interpretive system)のプロファイリング・ツールとしては役に立ちません。 つまり、VM プロファイラーは開発者にとっては役立ちますが、 インタプリタ・システム(interpretive system)のユーザーにとっては役に立ちません。

プロファイラーの出力は次のとおりです: 各基本ブロック(少なくとも 1 回実行される)について、その基本ブロックとそのすべてのサブシーケンスの動的実行回数を出力します。 例:

       9227465  lit storelocal 
       9227465  storelocal branch 
       9227465  lit storelocal branch 

これは、 ‘lit storelocal branch’ で構成される基本ブロックは 9227465 回実行されるということを示しています。

この出力をさまざまな方法で組み合わせることができます。 たとえば、 vmgen-ex/stat.awk は、 動的実行(dynamic execution)や、静的発生(static occurence)や、 プログラムごとの発生を参照して、 指定のシーケンスの発生を合計します。 例：

      2      16        36910041 loadlocal lit 

これは、 シーケンス ‘loadlocal lit’ が 2 つのプログラムの 16 か所で発生し、 36910041 回実行されたことを示します。 これで、 スーパー命令(superinstructions)を任意の方法で選択できるようになりました(注意: コンパイルの時間制約と空間的制約により、 スーパー命令の数は通常 100 ～ 1000 に制限されることに注意してください)。 これを完了すると、 vmgen/seq2rule.awk によって、 上記形式行が Vmgen 入力ファイルにインクルードできるルールに変換されます。 このスクリプトではすべてのプレフィックスが定義されていることは保証されないため、 プレフィックスは他の方法で定義する必要があることに注意してください。 したがって、 プロファイルをスーパー命令(superinstructions)に変換するための全体的なスクリプトは以下のようになります:

awk -f stat.awk fib.prof test.prof|
awk '$3>=10000'|                #select sequences
fgrep -v -f peephole-blacklist| #eliminate wrong instructions
awk -f seq2rule.awk|            #turn into superinstructions
sort -k 3 >mini-super.vmg       #sort sequences

ここでは、 動的カウント(dynamic count)がシーケンスの選択に使用されます(ただし、 暫定的な結果では、 静的カウントの方が良い結果が得られることを示しています)。 3 行目は、 スタックに直接アクセスするため、 スーパー命令内で発生してはいけない命令を含むシーケンスを削除します。 動的なカウント選択により、 より長いシーケンスのすべてのサブシーケンス(プレフィックスを含む)が確実に発生します(サブシーケンスは少なくとも長いシーケンスと同じカウントを持つため)。 最後の行でのソートにより、 プレフィックスの後ろで長いスーパー命令が確実に発生するようになります。

ただし、 これを使用する前に、 あなたにはプロファイラーが必要です。 Vmgen は file-profile.i を生成することでその作成をサポートします。 ほぼそのまま使用できるラッパー・ファイル vmgen-ex/profile.c も必要です。

プロファイラーは、すべての VM 制御フロー変更のターゲットを(実行中は SUPER_END を通じて、 フロント・エンドでは BB_BOUNDARY を通じて)記録し、(SUPER_END を通じて)ターゲットにされた変更の頻度をカウントすることによって機能します。 プログラムの実行後、 各 VM 基本ブロックが正しいカウントになるように数値が修正され(分岐を実行せずにブロックに入ってもカウントは増加しないという点を修正します)、 すべての基本ブロックのサブ・シーケンスが出力されます。 これらすべてを取得するには、 SUPER_END (および BB_BOUNDARY) を適切に定義し、 file にプロファイルを出力するときに vm_print_profile(FILE *file) を呼び出すだけです。

file-profile.i は逆アセンブラー・ファイルに似ており、vmgen-ex/profile.c で定義された変数と関数に加えて、 VM 逆アセンブラー用すでに定義されている VM_IS_INST を使用します(see VM disassembler)。

9.1 Floating point ¶

浮動小数点値をどのように扱うべきでしょうか？ あなたは整数/ポインターと同一のスタックを使用するべきでしょうか、 それとも別のスタックを使用するべきでしょうか？ このセクションでは、 実行速度の観点からこの問題について説明します。

より単純なアプローチは、 別の浮動小数点スタックを使用することです。 これにより、 整数/ポインターのサイズを考慮せずに FP 値のサイズを選択できるようになり、 多くのパフォーマンスの問題を回避できます。 主な欠点は、 これには FP スタック・ポインターが必要であることです(そして、 これは 386 アーキテクチャーのレジスター・ファイルに収まらない可能性があり、 パフォーマンスが多少低下しますが、 他のオプションを考慮すると比較的わずかです)。 別の FP スタック(スタック・ポインタ fp を使用)を使用する場合、 fpTOS の使用はほとんどのマシンで役に立ちますが、 一部のマシンでは fpTOS レジスタがメモリに配置(spill)されるため、 fpTOS を使用すべきではありません。

もう一つのアプローチは、 整数/ポインターと浮動小数点値で 1 つのスタック(たとえば、sp によってポイントされる)を共有することです。 spTOS を使用しなくても、 これは問題ありません。 spTOS を使用する場合、 コンパイラーはその変数を整数レジスターに入れるか浮動小数点レジスターに入れるかを決定する必要があり、 他の型の操作はほとんどのマシンで非常に高価になります(整数レジスターと FP レジスターの間で値を移動するため、 かなり高価です)。 一方の型の値を、 もう一方の型の 2 つの値(double 型)から合成する必要がある場合、 事態はさらに興味深いものになります。

この問題を回避する 1 つの方法は、Vmgen でサポートされている spTOS を使用せず、 明示的なスタックのトップ変数(整数用に 1 つ、 FP 値用に 1 つ)を使用し、 一種の アキュムレータ+スタック・アーキテクチャを使用することです。 (たとえば、 Ocaml バイト・コードはこのアプローチを使用します)。 ただし、 これは大きな変更であり、 その影響範囲は完全には明らかにはなっていません。