一人一党党

一人一人の、一人一人による、一人一人のための政治制度を!

スタックマシンで文明崩壊後のセルフアセンブラ

これは 言語実装のカレンダー | Advent Calendar 2024 - Qiita の22日目の記事です。

1日目の記事 でやり残した、 スタックマシン上でのセルフホスティング環境構築ですが。 やはりforthでは新味がないし、 今年のこのカレンダーに間に合わせたいので、 手っ取り早くstage0riscを移植してみました。 stack-isaディレクトリ に成果物があります。

命令セットアーキテクチャ

前記事である1日目と同様に、まずは仮想マシンエミュレータを製作します。 前記事との違いは、CPUの命令セットがスタックマシンのものであることです。 スタックマシンとして比較的新しい命令セットアーキテクチャである The Zylin ZPU を元に、コード密度を代償にしてハードウェア寄りの簡略化をしてみました。

固定長命令セットで無限の即値・オペコード

スタックマシン命令セットの長所のひとつは、 スタックに積まれた値を暗黙のオペランドとして使うことで、 命令の長さを短くできることです。 しかしこの長所をハードウェアや、 レジスタマシンとスタックマシン - ひとり勉強会 で述べられているように、インタプリタで実際に活かすには問題があります。

命令長は固定である方が、 より高速なハードウェア実装やインタプリタ実装ができます。 ハードウェアであれば、命令長が揃っていないと、 前の命令を処理する間に並行して次の命令を読み込む、 パイプライン処理が難しくなります。 インタプリタでも、命令長がメモリ境界に合っていないサイズだと、 命令の読み出しに複数のメモリアクセスが必要となったりなど、不都合が出ます。 命令長を揃えるためには、最も長い命令に命令長を合わせる必要があります。 ここで、スタックに積まれたオペランドを省略するだけでは、 短くならない命令があります。 即値をオペランドとする命令です。 テキストファイルであるソースコードを扱うため、 stage0riscの各プログラムでは文字コードであるASCIIコードを扱いますが、 それらは8bitの即値です。 あるいは、分岐命令では飛び先アドレスを指定しますが、それらも即値です。 最悪バイナリエディタで16進コードを手打ちする場合を想定しているため、 stage0riscの各プログラムは小さいのですが、 それでも256バイトを越えるものがあり、 プログラムカウンタ相対アドレッシングでも、 前方後方合わせて10bit必要です。 また、命令の種類を指定するオペコードの大きさは、命令の種類数に直結します。 固定長命令セットだとオペコードの大きさに上限があるため、 後から命令の種類を追加するのが難しくなります。

そこでZPUでは、即値ロード命令が連続している場合は、 スタック先頭の値に左シフト演算を掛け、 空いた下位ビットを後続の即値ビットで満たします。 これにより、あたかも即値ビットを繋げた一つの即値命令かのように解釈でき、 即値の大きさの制限を取り払うことができます。

#ZPU
1xxxxxxx  #最上位ビットが立っていると、7bit即値xxxxxxxをスタックに積む。
1yyyyyyy  #前の命令も即値ロード命令なので、スタック先頭の値下位にビットを付け足す。
#以上2バイトで、一つの14bit即値xxxxxxxyyyyyyyがスタックに積まれる。

ただしこの方法では、同じビット列の即値ロード命令でも、 新しい値をスタックに積むのか、 スタックの高さを変えずにスタック先頭の値を更新するのか、 前の命令が即値ロード命令か否かで動作が異なります。 ZPUではそのための状態フラグをCPUに追加しています。 なので、エラーや割り込み処理でCPUの状態を保存・復元したいとき、 プログラムカウンタだけでなく状態フラグも保存・復元しなければなりません。 当のZPUでは、高々1bitの状態フラグの為に ワード単位の保存領域を消費することを避けるため、 割り込みへの応答が遅れることを覚悟で、 フラグが立っている間の割り込みを禁止しています。 なので当記事では、状態フラグを追加せずに、 即値ロードにスタック先頭の値を使用するか否かを、 命令ビット列に織り込みます。

#当記事(中途)
01xxxxxx  #最上位ビットが立ってないなら、新しい値を積む。
11yyyyyy  #最上位ビットが立っているなら、スタック先頭の値下位にビットを付け足す。
#以上2バイトで、一つの12bit即値xxxxxxyyyyyyが積まれる。

代償として、ZPUで状態フラグとして扱っていたものを命令ビット列に織り込んだ分、 一つの命令で加えられる即値ビットの長さが7bitから6bitに減ってしまいました。

固定長命令で即値の大きさの制限を取り払ったのですから、 もう一つの制限であるオペコードの大きさも、同じ方法で取り払うことができます。

#当記事(中途)
00cccccc  #上位2ビット目が0だったら、6bitオペコードccccccで指定された演算を行なう。

01xxxxxx  #即値をスタック先頭に積む。
10yyyyyy  #最上位ビットが立っているので、スタック先頭の値を利用する。
#上位2ビット目が0なので、一つの12bit即値xxxxxxyyyyyyをスタック先頭に戻すのではなく、12bitオペコードで指定された演算を行なう。

今回スタックマシンのエミュレータを製作したところ、 前記事で製作したレジスタマシンよりも、必要な命令種類が多かったのは、 私には予想外でした。 確かに一般的なレジスタマシンでは、 「縮小命令セットコンピュータ」 として設計されたものでも、 RISC-V命令セットの 基本サブセットRV32Iで37種ほどの命令種類が定められています。 しかしよく見ると、算術命令を中心に多くの命令で、 オペランドにレジスタしかとらないものと即値をとるものの二種が用意されています。 他方、多くのスタックマシンでは、即値をオペランドにとる命令は殆ど見られません。 即値オペランドが演算に必要なら、 即値ロード命令でスタックに積んでから演算命令を実行します。 前記事で製作したレジスタマシンでは、 一般的なスタックマシンと同様に即値を用いる命令を省いたため、 今回のスタックマシンを下回る数の命令種にできたようです。 後述しますが、 現時点で1バイト当たり6bitあるオペコードは最終的には5bitに減り、 1バイトで表現できる演算命令の種類数に余裕がなくなります。 最終的には不要になりましたが、このオペコード拡張の仕組みは、 仮想マシンの製作に於いて心の余裕を私に与えてくれました。

レジスタマシンのオペランドフィールド・オペコードフィールドに当たるもの

前記事でも述べたように、 レジスタマシンとスタックマシンとの違いは、 各命令でのオペランドの指定方法が、レジスタ番号なのか、 スタック先頭との相対位置なのか、でしかありません。 にも拘らず、 全ての命令が全ての汎用レジスタにアクセスできるレジスタマシンと違って、 スタックマシンでは 殆どの演算命令がスタック先頭からの最低限の要素数の値にしかアクセスできません。 そこで、スタックの奥の値にアクセスする命令が 大抵のスタックマシンには用意されているのですが。 それらの命令ではスタック先頭との相対位置が引数として必要で、 その引数をスタックに積むために即値ロード命令などが別に必要となります。 レジスタマシンではこの動作を 命令内のオペランドフィールドひとつで行なっていることを考えると、 スタックマシンでの 「相対位置のロード + スタック奥にアクセス」の2命令は冗長です。 なので、この動作を単一命令に纏めた1オペランド命令が、ZPUには用意されています。

ところで、1オペランド命令としては既に即値ロード命令があります。 演算命令は0オペランド命令ですが、 オペコード拡張方法が即値ロード命令でのオペランドの拡張と同じことから考えると、 オペコードを引数としてとる1オペランド命令と見做すことができます。 そして、命令形態の種類が少ないほど、 ハードウェアやインタプリタの実装が簡略になります。 なので当記事ではこれらを、 同一の大きさ(5bit)のオペランドフィールドを持つ 1オペランド命令として実装します。

#当記事(実装済み版)
76543210
e00xxxxx  #オペランドで指定された演算を行なう。
e01xxxxx  #スタックから値を取り出し、スタック先頭からオペランドで指定された相対位置に書き込む。
e10xxxxx  #スタック先頭からオペランドで指定された相対位置にある値を読み込み、スタックに積む。
e11xxxxx  #オペランドを即値としてスタックに積む。
#eがセットされていたら、スタックから値をとりだして、オペランドの拡張に使う。

スタックをレジスタマシンのレジスタに当たるものと考えると、 これら4種の命令群はレジスタマシンでの オペランドフィールド(即値、入力元レジスタ、出力先レジスタ)や オペコードフィールドと同じ働きをします。 勿論、命令毎に種類と数が固定されている レジスタマシンでのオペランドフィールドと違い、 これらは独立した命令であり、自由に入れ替えたり、 省略や複数個の命令列に置き換えることができます。 例えば、スタック奥読み出し命令の代わりに即値ロード命令を使うことで、 前記事のレジスタマシンでは省いた、 即値をオペランドにとる命令と同じことができます。 あるいは、単一の即値ロード命令の代わりに複数個の命令を使うことで、 メモリ間接参照などの複雑なアドレッシングモードと同様の動作が得られます。 ZPUでは スタックポインタを上げ下げするものも1オペランド命令にしていますが、 スタックポインタなんてレジスタマシンにはない以上、 スタックポインタの上げ下げが無くても ( 2024年12月22日修正: スタックポインタを上げ下げするのではなく、 スタックの奥の値のメモリアドレスを取得する命令でした。 それでも、メモリアドレスなんてレジスタにはない以上… ) レジスタマシンと同等の動作には十分です。 命令形態が一種類で揃っているのもあり、当記事ではこれを採用します。

スタックの数

前記事で述べたように、文明崩壊後のメモリ容量は非常に小さいと思われます。 なので、メモリはできるだけ有効活用したいところであり、 使い切ってないのにシステムが動かなくなるのは避けねばなりません。 この点、冒頭に述べたforthなど、スタックが複数必要なシステムは不利です。 どれかのスタック領域が満杯になると、 他のスタック領域を使い切っていないのにシステムが動けなくなります。 なので、当記事ではスタックの数を最低限の一本にしました。

移植した結果

あとは、この仮想マシンにstage0riscを移植するだけです。 レジスタマシンからスタックマシンへの移植ですが、 先に述べたように、レジスタマシンと同等の動作が冗長にならないように スタックマシンを製作したので、アルゴリズムの変更は特には行なっていません。 両者のソースコードを見比べると、ラベル名が殆ど使い回されているのが分かるかと。 コーディング作業で困ったのは、変数をマクロで扱えないことでした。 スタックの値はスタック先頭からの相対位置で参照するため、 スタックが伸び縮みする度に相対位置を計算し直す必要があり、 固定の値しか扱えないマクロでは参照できません。 それでもなんとか移植した結果、 当記事のスタックマシンに移植したイメージファイルの合計サイズは、 stage0riscでの合計サイズ996バイトの76%に当たる761バイトになりました。 スタックマシン側の方を基準に100%とすると、 stage0risc側は31%ほど大きいということになります。 Virtual Machine Showdown: Stack Versus Registers によると、スタックマシンであるJAVA仮想マシンのイメージファイルを レジスタマシンのものに変換した結果、26%ほどサイズが増加したそうです。 当記事では逆にレジスタマシンのものをスタックマシンのものに変換したのですが、 似た結果になったのは興味深いところです。

やり残しは続くよ

変数の実装を「人間コンパイラ」に丸投げしたのは、 スタックマシンを取り上げた記事として大きな欠陥でしょう。

勿論、スタックマシン上で変数を扱う言語処理系は、無いわけではありません。 しかし、そこで使われている方法が、 スタックマシンの構造を活かした効率の良いものかは、別問題です。

全ての汎用レジスタを同一コストでアクセスできるレジスタマシンと違い、 スタックマシンでのスタックのアクセスコストは、 スタック先頭からの距離により異なるように作られています。 一部を除いてレジスタにしかアクセスしないレジスタマシンでの命令と同様に、 スタックマシンでの命令は一部を除いて スタック先頭から順番にしかアクセスしないからです。 大きな相対位置の指定には大きな即値フィールドのコストが伴うので、 x86命令セットなどで用いられている、 スタックの特定のアドレスを指すレジスタ 「ベースポインタ」からの相対位置を用いて変数を実装する方法は、 スタックマシンのアクセスコスト構造とは少しズレがあると私は考えます。 ベースポインタレジスタを汎用レジスタとして目的外利用する最適化が、 当のx86向けコンパイラで普及しているのも、これを避けた理由のひとつです。 文明崩壊前に再興するであろうスタックマシンでは、 過去の遺物と化したベースポインタが省かれていると、私は予想します。 対して、スタック先頭からの相対位置でアクセスする方法は、 少なくとも仮想マシンインタプリタの実装では、 後述のStack Cachingを適用したとき、 小さな相対位置を即値オペランドで指定する命令で物理レジスタを活用できます。 なので、スタックの奥にアクセスする命令として当記事ではこちらを選択し、 命令セットを最小限にするため、ベースポインタを省きました。

forthにも変数はありますが、単純な実装の場合、 変数はスタックではなく固定アドレスであるメモリ上の「辞書領域」に割り付けます。 レジスタマシンでも使える移植性の高いこの手法は裏を返せば、 マシンの構造を活かしたものとは到底言えません。

以上により、スタックマシンの構造を活かした変数実装には、 スタックの伸び縮みを把握するコンパイラが必要になるようです。 勿論、stage0riscでコンパイラと称するものは、 最適化機能などない低機能のアセンブラに過ぎません。 しかし、GNU assemblerには "CFI directive" という疑似命令があり、 スタックの状態をプログラマから教えてもらうようです。 これを真似れば、当記事で製作したセルフ開発環境を僅かに拡張するだけで、 変数位置の計算を自動化できるかも知れません。 現在のstage0riscでニーモニックを実装しているマクロでは、 各ニーモニックの機械語ビット列しか定義していませんが、 スタックの増減を知らせる疑似命令も各ニーモニックのマクロに追加すれば、 後続のバイナリ生成プログラムでスタックの伸び縮みを把握できそうです。

他にやり残したこととしては、折角の仮想スタックマシンだし、 スタックの奥にアクセスする命令の設計で行なった選択の利点を享受するためにも、 Stack Caching for Interpreters 辺りのスタックマシン用高速化手法を試したいところです。