スタックマシン
スタックマシンの命令セットには、直接ハードウェアで実装するのではなく、仮想機械でインタプリタ的に解釈することを意図したものもある。仮想スタックマシンのインタプリタは相対的に構築が容易である。これは、メモリアドレスとして基本的にスタックのトップだけを意識すればよいという性質に起因している。また命令の種類も相対的に少ない。
最近では計算負荷の並列性が高まっており、この欠点は過去のものとなりつつある。
スタックトップの内容を追跡する事によって、この欠点は克服されている。例えば、スタックトップ2個がレジスタ化されているインタプリタで"A B C - /"という式(逆ポーランド記法の場合。通常記法での"A / (B - C)"に当たる。)を計算するとき、"Aのロード"と"B C - の演算"の両方とも、結果がレジスタに格納される。レジスタ・リネーミングを行う物理プロセッサでは、レジスタ間演算の依存関係を認識してアウト・オブ・オーダー実行が行われる。このため、"Aのロード"と"B C - の演算"に依存関係がなく並べ替えが可能であることを物理プロセッサは認識し、"Aのロード"の途中で"B C - の演算"を挟む。Mopsをx86_64(レジスタマシン)向けにコンパイルするiMopsでは、コンパイル時に追跡可能なスタックをノードとするノードグラフを対象にレジスタ割り当てを行い、プロセッサによる命令並べ替えを助ける。物理スタックマシンについても、レジスタマシンで論理レジスタをレジスタ・リネーミングするのと同様に、スタックなどのメモリ領域をリネーミングすることでTomasuloのアルゴリズムの実装が可能だと言われている。
業界には、一時変数や局所変数の操作でレジスタマシンよりもスタックマシンの方がデータキャッシュに頻繁にアクセスするという見方もある。一方、それとは全く逆の主張もある。ここでは、スタックマシンにおけるメモリアクセスパターンを理解する必要がある。
スタックマシンでは一時変数がメモリに置かれることが多いのに対し、多数のレジスタを持つマシンでは一時変数はレジスタに保持され続ける。ただし、多数のレジスタがあるということは、割り込みやコンテキストスイッチでセーブ/リストアすべきデータが多いということも意味する。一時変数がメモリに置かれれば、データキャッシュへのアクセスは増えるが、その度合いはスタックのトップをどれだけレジスタ化しているかで変化するし、プロシージャコールが入れ子になる頻度や割り込み発生頻度によっても変わってくる。
スタックのトップ部分をレジスタ化していない単純な実装では、レジスタマシンよりも性能が低くなる。例えば X+1 という式はスタックマシンでは 'Load X; Load 1; Add' という3命令になる。これは、「Xをロードしてスタック(メモリ)にプッシュ。1をスタックにプッシュ。スタックから2つの値をポップしてそれらを加算し、結果をスタックにプッシュ」という意味であり、5回データキャッシュにアクセスすることになる。スタックのトップがレジスタ化されていても、最悪ケースではデータキャッシュのアクセス回数は減らない。レジスタマシンでは最適化によってなるべく値をレジスタに保持しようとするので、最初にXをロードするだけで済む。一方で、レジスタマシンはプロシージャコールの入れ子で一時変数として使っているレジスタの内容を一斉にメモリにセーブする必要が生じる。
仮想スタックマシン向けにプログラムをコンパイルすると、レジスタマシン向けよりも(コードサイズは小さくとも)命令数が多くなる。仮想スタックマシンを実装したインタプリタは、命令コードに従って分岐して対応する命令コードの処理を行う。また、スレッデッドコードで実装した場合も頻繁に分岐を繰り返すことになる。インタプリタの分岐先は命令コードの種類という膨大な数であり、その様な分岐を効率よく行うため、間接分岐命令が使われる。ところが初期の分岐予測機構では、間接分岐命令への対応が欠けている。このため、仮想スタックマシンの命令をデコードして実行するたびに、ホストマシンのパイプラインは誤った分岐先を投機実行し、修正のためリスタートすることになる。個々の命令が単純で命令数が多くなるため、そのような状況はスタックマシン以外の仮想機械よりも仮想スタックマシンで発生しやすいと言われている。AndroidのDalvik仮想マシンはJavaを実行するが、本来のJava仮想マシンが8ビットのスタックマシンなのに対して、16ビットのレジスタマシンとなっている。これにより命令数を少なくし、命令コードディスパッチでのストールを低減している。算術命令は4ビット(以上)のオペランドを使って直接局所変数をフェッチまたはストアすることができる。
ただし、分岐予測が成功している場合、パイプラインのリスタートは生じず、予測と実行後の分岐先を比較するALU演算程度まで分岐命令のコストは低下する。Java仮想マシンインタプリタの普及に伴い、インタプリタにも対応できる分岐予測器を積んだプロセッサが普及しており、この問題でのレジスタマシンとスタックマシンとの差は縮まっている。
スタックマシン型の命令セットでは、例えば加算 (ADD) 命令はスタック上のトップにある2つの値を暗黙のうちにオペランドとして使用し、それらの和をスタックのトップに格納する。オペランドとして使用した値はスタックから取り除かれ(ポップ)、和をスタックのトップに置く(プッシュ)。ほとんどの命令は命令コードだけで構成され、レジスタ番号やメモリアドレスや即値を指定する必要がない。演算を行う場合、先にスタック上に演算対象の値をプッシュし、その後に演算命令を実行することになる。これは逆ポーランド記法と呼ばれる数式の表現方法と同じである。この場合、演算命令は容易に3つ以上の値を対象とするよう拡張可能である。メモリ上の任意のアドレスにあるデータをスタックにプッシュする命令や即値をスタックにプッシュする命令が必要となる。
スタックマシンと対比されるレジスタマシンは、高速で小さいレジスタファイルを持ち、一時的な値をレジスタに保持する。その中でもアキュムレータマシンはレジスタを1つだけ持ち、そのレジスタとオペランドで指定したメモリ位置との間で演算を行う。初期のコンピュータには一時レジスタを持たず、常にメモリ間で演算を行うものもあった。
ソフトウェアで解釈される仮想スタックマシンの例を挙げる。
SECDマシン
UCSD Pascal p-machine
Java仮想マシン命令セット
.NET Framework 環境における共通中間言語命令セットおよびその仮想機械である VES(仮想実行システム)
Forth言語処理系。特にスレッデッドコードで実装されているもの。
アドビのPostScript
サン・マイクロシステムズの Sun Ray スマートカードの定義作成のための SwapDrop 言語
CPython バイトコードインタプリタ
最近のコンピュータでは、データをフェッチするのにかかる時間は、ALUで演算を行うのにかかる時間よりも長い。したがって、メモリ上のデータが実際に必要になるよりも十分前にフェッチを開始すれば、命令パイプラインをストールさせることなく高速に処理を継続できる。アウト・オブ・オーダー実行方式では、複数の命令をプロセッサが調べてそのような動作をしている。アウト・オブ・オーダー方式でなくともレジスタマシンであれば、コンパイラが賢ければそのようなコードを生成することができる。この命令スケジューリングには使っていないレジスタがなければならない。従って純粋なスタックマシンにはこのような命令の並べ替えは不可能である。例えば A - B という式があるとき、スタックマシンではAとBをロードしてスタックにプッシュしてから即座に減算を行う。途中に別の命令を挟もうとしても、スタックマシンの命令は基本的にスタックをいじるので、ほとんど何もできない。スタックマシンでは、メモリからのロード遅延を隠蔽できるほど深いパイプラインでアウト・オブ・オーダー実行を行うか、ハードウェアマルチスレッディングでスレッドを切り換えてロード遅延を隠蔽するしかない。ユニシスのA9システムでは後者の方式を実装している。