スタックマシン

スタックマシンとは

スタックマシンは、計算機科学、計算機工学、プログラミング言語実装において、メモリをスタック構造で扱う計算モデルを指します。これは、データの出し入れを後入れ先出し（LIFO）で行うスタックを利用する点が特徴です。また、スタックマシンは「0オペランド」命令セットを持つマシンとしても知られています。

計算のスタックモデル

理論的な計算モデルとしてのスタックマシンは、ランダムアクセス可能なメモリを持たず、LIFOのスタックのみを利用します。このモデルは、複数のスタックを持つことができ、各時点での状態はリード状態かライト状態のいずれかです。初期入力はスタック1に与えられ、他のスタックは空の状態から始まります。1つのスタックのみを持つスタックマシンは、計算能力が限られていますが、複数のスタックを持つスタックマシンはチューリングマシンと同等の能力を持ちます。

スタックマシン型命令セット

スタックマシン型の命令セットでは、演算はスタックのトップにある値を対象に行われます。例えば、加算命令はスタック上の2つの値をポップし、その和をスタックにプッシュします。命令コードのみで構成されるため、レジスタ番号やメモリアドレスを指定する必要がありません。演算を行う前に、演算対象の値をスタックにプッシュします。この方式は逆ポーランド記法と同じであり、3つ以上の値を対象とするように拡張可能です。

スタックマシンと対比されるのはレジスタマシンです。レジスタマシンは一時的な値をレジスタに保持します。アキュムレータマシンはレジスタを1つだけ持ち、そのレジスタとメモリ間で演算を行います。初期のコンピュータには一時レジスタがなく、メモリ間での演算のみを行うものもありました。

スタックマシンの実装方式には、レジスタファイルのみをスタックとして利用する方法と、メモリ上にスタックを持ちスタックトップを指すレジスタを持つ方法があります。また、稀にメモリ上のスタックとレジスタファイルによるスタックを別々に持つ実装も見られます。

回路素子の高速化に伴い、スタックを階層構造のキャッシュに収める実装も登場しています。スタック内のオペランドが使われる順序は、スタックトップから下方へ積まれている順序と一致するため、スタックトップを優先的に高速な記憶素子に収めることで、オペランドのプリフェッチが実現されます。

スタックベースの命令セットを持つマシンは、複数のスタックを持つことがあります。データスタックとリターンスタックを分離することで、スタック管理処理を排除し、動作を高速化できます。この方式は、バロースB5000、Forth、PostScript、Java仮想マシンなどで採用されています。

利点

オブジェクトコードのコンパクトさ

スタックマシンは、オペランドを指定する必要がないため、個々の命令が小さく、コード密度が高くなります。分岐命令や即値のロード命令もスタック上の値をオペランドとすることで、命令を小さくできます。レジスタマシンでは、ALU命令で2つまたは3つのレジスタを指定する必要があり、1命令あたり少なくとも16ビット以上が必要です。アキュムレータマシンはオペランドが1つですが、複雑な式を計算する際に一時変数への退避が必要になります。スタックマシンでは、逆ポーランド記法の性質から、一時変数への退避は不要です。

コンパイラの単純さ

スタックマシン向けのコンパイラは、レジスタ割り付けを考慮する必要がなく、コード生成が容易です。加算命令やインデックス付きロード命令なども、複雑な式や入れ子のプロシージャ呼び出しであっても同じ命令コードを使うことができます。この単純さは、メモリ容量の小さなマシンでもコンパイラを利用可能にし、オペレーティングシステムを高水準言語で開発することを可能にします。

インタプリタの単純さ

スタックマシンの命令セットは、仮想マシンで解釈することを意図したものもあります。仮想スタックマシンのインタプリタは構築が容易であり、命令の種類も少ないため、メモリアドレスはスタックトップだけを意識すればよいという性質に起因します。

プロセッサの状態数が少ない

データスタックを持つマシンで必須となるレジスタは、スタックポインタと命令ポインタのみであり、コンテキストスイッチや割り込みの際にセーブすべき状態情報が少なくなります。

高速なオペランドアクセス

オペランドを指定する領域が命令内に存在しないため、命令の読み出しと並行してオペランドの読み出しが可能です。スタックトップを優先してキャッシュすることで、オペランドのプリフェッチが実現されます。

欠点

メモリ参照が多い

スタックマシンでは、一時変数がメモリに置かれることが多く、レジスタマシンよりもデータキャッシュへのアクセス頻度が高くなる場合があります。しかし、これはスタックのトップをどれだけレジスタ化しているかによって変化します。スタックのトップをレジスタ化していない単純な実装では、レジスタマシンよりも性能が低くなります。

共通部分式除去のコストが高い

レジスタマシンでは、共通部分式の結果をレジスタに保持して再利用できますが、スタックマシンでは同じことを行うのが難しく、一時変数への退避やスタック操作が必要になります。スタックマシン向けのコンパイラでは、共通部分式除去などの最適化は行われていないことが多いです。

コード順序の厳密性

純粋なスタックマシンでは、命令の並べ替えが難しく、アウト・オブ・オーダー実行ができません。メモリからのロード遅延を隠蔽するために、深いパイプラインやハードウェアマルチスレッディングが必要になります。

高速レジスタを隠蔽する

スタックマシンでは、レジスタファイルの効率的な利用が難しい場合があります。命令が明示的にレジスタを指定できれば、コンパイラでレジスタ利用を最適化できる可能性があります。

仮想スタックマシンの問題点

仮想スタックマシンは、レジスタマシン向けよりも命令数が多くなる傾向があります。インタプリタでの頻繁な分岐により、ホストマシンのパイプラインが誤った分岐先を投機実行し、リスタートすることがあります。

ハイブリッド方式

純粋なスタックマシンは構造を持つデータオブジェクトへのアクセスが苦手なため、レジスタマシンの一部機能を組み込んだハイブリッド方式が用いられることがあります。また、レジスタマシンのアーキテクチャにスタック操作を追加する方式も一般的です。第2世代スタックマシンでは、メモリアドレッシングを肩代わりするアドレスレジスタ群を備えています。

実用化されたスタックマシン

ハードウェアで直接実行されるスタックマシン型命令セットの例としては、GreenArraysのGA144、バロースB5000、インモストランスピュータなどがあります。また、仮想スタックマシンの例としては、Java仮想マシン、.NET環境のVES、CPythonバイトコードインタプリタなどがあります。

コールスタックとスタックフレーム

現代のコンピュータでは、コールスタックが局所変数の格納場所やサブルーチンからの復帰情報格納に使われています。サブルーチンコールのたびにスタックフレームが作成され、プロシージャや関数の局所変数へのアクセスが提供されます。バロースB5000では、ハードウェアでスタックフレームを遡る手段を提供していましたが、現在は一般的ではありません。Forthのような単純な言語では、スタックフレームはリターンアドレスのみを格納します。

まとめ

スタックマシンは、そのシンプルな構造と高いコード密度から、特定の用途で有効な計算モデルです。しかし、メモリ参照の多さや最適化の難しさといった課題も抱えています。近年では、ハイブリッド方式や仮想マシンの進化により、これらの課題も克服されつつあります。スタックマシンの理解は、計算機科学の基礎を深く理解する上で非常に重要です。

もう一度検索