Loading AI tools
スタックマシン (stack machine) とは、メモリがスタックの形式になっている計算モデルを意味する。 スタックマシンを実装あるいはシミュレートしている実在のコンピュータもスタックマシンと呼ぶ。
 |
加えて、スタックマシンは「0オペランド」(zero-address instruction と表現する文献[1]もある)命令セットのマシンも意味する。0オペランドマシンでは、命令は暗黙のうちにスタックのトップおよびトップ近傍にある値を使って演算を行い、結果はやはりスタックに積む。
スタックマシン（0オペランド命令セット）がアキュムレータマシン（1オペランド命令セット）やレジスタマシン（2オペランド命令セット、3オペランド命令セット）に比較して優れているのは、コード密度が一般により高い点である。
尚、コールスタックを使って入れ子になったサブルーチン呼び出しの局所変数群を管理する方式のコンピュータを、普通スタックマシンとは呼ばない。
計算機科学のオートマトン理論における「スタックマシン」は、メモリにランダムアクセスすることができず、LIFO型のスタックしか持たない計算モデルである。これは純粋に理論上のモデルであり、実在のコンピュータではメモリは任意のアドレスを指定してアクセスできる。
スタックマシンはいくつかのスタックを持つ。プログラムの初期入力はスタック1の初期状態として与えられ、他のスタックは初期状態では空である。スタックマシンの各時点の状態はリード状態かライト状態であり、各状態にはスタックからリード（ポップ）すべき値の個数かスタックにライト（プッシュ）すべき値の個数が付与される。さらにライト状態には書き込むべきシンボルが指定され、次に遷移すべき状態が指定される。リード状態ではアルファベットそれぞれについて、リード結果としてその文字を読んだときに遷移すべき次の状態が指定される。さらにリード状態ではスタックが空だったときの遷移先状態も指定される。スタックマシンは特別な停止状態に到達したとき停止する。
スタックを1つしか持たないスタックマシンは、計算モデルとしては非常に弱い。例えば、1-スタックマシンでは、0n1n（0の並びの後に同じ個数の1が並ぶ言語）のような単純な言語も認識できない。1-スタックマシンの計算能力は、有限オートマトンよりも高いが、決定性プッシュダウン・オートマトンよりも低い。
一方、複数のスタックを持つスタックマシンはチューリングマシンと等価である。例えば、2-スタックマシンでは、チューリングマシンをエミュレートできる（チューリングマシンのヘッド位置から左側のテープをひとつのスタックが代替し、右側のテープをもうひとつのスタックが代替する）。
スタックマシン型の命令セットでは、例えば加算 (ADD) 命令はスタック上のトップにある2つの値を暗黙のうちにオペランドとして使用し、それらの和をスタックのトップに格納する。オペランドとして使用した値はスタックから取り除かれ（ポップ）、和をスタックのトップに置く（プッシュ）。ほとんどの命令は命令コードだけで構成され、レジスタ番号やメモリアドレスや即値を指定する必要がない。演算を行う場合、先にスタック上に演算対象の値をプッシュし、その後に演算命令を実行することになる。これは逆ポーランド記法と呼ばれる数式の表現方法と同じである。この場合、演算命令は容易に3つ以上の値を対象とするよう拡張可能である。メモリ上の任意のアドレスにあるデータをスタックにプッシュする命令や即値をスタックにプッシュする命令が必要となる。
スタックマシンと対比されるレジスタマシンは、高速で小さいレジスタファイルを持ち、一時的な値をレジスタに保持する。その中でもアキュムレータマシンはレジスタを1つだけ持ち、そのレジスタとオペランドで指定したメモリ位置との間で演算を行う。初期のコンピュータには一時レジスタを持たず、常にメモリ間で演算を行うものもあった。
スタックマシンの実装方式は2つあり、レジスタファイルのみを小さなスタックとして利用する実装と、スタック自体はメモリ上にあって、スタックのトップを指すレジスタを持つ実装である。後者の例としては、バロース B5000 や HP 3000 がある。稀に、メモリ上のスタックとレジスタファイルによる小さいスタックを別々のスタックとして持つ実装もある。B5000の場合、スタックトップの2つのデータは CPU レジスタに割り当てられ、残りスタックデータをメインメモリに割り当てていた[1]。
回路素子の高速化によりメモリアクセスなどの配線遅延が問題となるに連れて、スタックを階層構造のキャッシュに収める実装が現れた。明示的なロード命令を用いない限り、スタック内のオペランドが使われる順序は、スタックトップから下方へ積まれている順序と一致する。このため、スタックトップから優先してより高速の記憶素子に収められた状態を保つだけで、オペランドの強力なプリフェッチが実現され、配線遅延が隠蔽される。仮想スタックマシンの多くでは、スタックトップはメモリ領域ではなくホストマシンのレジスタファイルで実装されるレジスタで実現されている。FPGA上のJAVAプロセッサであるJOPでは、レジスタファイルよりさらに高速で小さい記憶素子である、命令パイプライン上のラッチ回路をスタックトップ2個に充てている。
スタックベースの命令セットを持つマシンは、複数のスタックを持つことがある。2つのスタックを持つ場合、一方を「データスタック」、もう一方を「リターンスタック」と呼び、データスタックはデータの処理に使われ、リターンスタックはサブルーチンコールの戻りアドレスを保持するのに使われる（コールスタックとも）。データスタックとリターンスタックを分離すると、スタック管理処理の大部分を排除して、全体の動作を大幅に高速化できる。このスタックを2つ持つという方式は独自に3回発明されている(バロース B5000、Forth、PostScript)。また、Java仮想マシンでも使われている。
ヒューレット・パッカードの関数電卓が有名だが、一種のスタックマシンを操作モデルとしている電卓がある。プッシュに相当する「Enter」キーが特徴である。具体例で説明すると、加算を行う際は、「数値1」「Enter」「数値2」「+」の順に操作する。この操作で、まず2つの数値がスタックにプッシュされた後、加算のためにポップされ加算され結果がプッシュされる。逆ポーランド記法(順)の電卓、と呼ばれている。
オペランドとしてレジスタを使うマシンは、容易にスタックマシンをシミュレートできる。このようなシミュレーションを「仮想スタックマシン」とも呼ぶ。
利点
- オブジェクトコードのコンパクトさ
- オペランドを指定する必要がないため、個々の命令が一般に小さく、6ビット程度で済む。分岐命令、即値のロード命令、ロード/ストア命令はオペランドを必要とするが、多くの場合それらの命令もスタック上の値をオペランドとすることで命令を小さくできる。前の命令の結果をスタックに自動的にプッシュすることで、次の命令でそれを暗黙のうちに利用できる。対照的にレジスタマシンでは、ALU命令で2つまたは3つのレジスタを指定するオペランドを必要とし、1命令あたり少なくとも16ビット以上を必要とする。アキュムレータマシンはオペランドが1つだが、複雑な式を計算する際に一時変数へ値を退避しなければならないので、余計なロード/ストア命令を必要とする。スタックマシンでは、逆ポーランド記法が括弧を使わないことからもわかるように、一時変数への退避が発生しない。
- プロシージャや関数の局所変数や引数にアクセスするため、スタックマシンにも一種のロード/ストア命令がある。スタックのトップのアドレスからのオフセットでアドレスを指定する場合やフレームベースを指すレジスタにオフセットを指定する場合などがある。レジスタマシンでは「レジスタ+オフセット」のアドレス指定に相当するが、一般にレジスタマシンの命令ではオフセットフィールドのビット幅が大きい。
- 1960年代、メインフレームであっても主記憶容量が小さかったため、コード密度を高くすることは重要な課題だった。初期のミニコンピュータやマイクロコンピュータでも同様だった。もっと最近では携帯機器へのソフトウェアのダウンロードで、ダウンロード時間短縮のためにコード密度を高くする必要が生じた。コード密度が高ければ、キャッシュメモリや命令プリフェッチの効果が高まる。組み込みシステムでは搭載するROMを小さくできる。ただし、コード密度を高めすぎると実行性能が低下することがある。
- バロースのアーキテクチャは、スタックマシンにタグ付きメモリを組み合わせたものである（各メモリワードの一部ビットでデータ型などを表す）。タグ付きメモリはオペコード（命令コード）の縮小に貢献している。つまり、整数や浮動小数点数といった区別はメモリワード自身が持っているので、命令コードで示す必要がない。スタックマシンであるためオペランドも少なく、結果として命令長が小さくて済むようになっている。
- コンパイラの単純さ
- スタックマシン向けのコンパイラは、相対的に単純であり、作成が容易である。特にコード生成は単純であり、前後関係を考慮する必要がなく、構文解析に容易に組み込める。レジスタ割り付けを考慮する必要がなく、定数参照や簡単なメモリ参照を最適化する必要がない。加算命令、インデックス付きロード命令、コール命令などは、複雑な式や入れ子のプロシージャ呼び出しであっても全く同じ命令コードを使うことができ、コンパイラが特殊ケースを考慮する必要がない。
- コンパイラが単純ということは、メモリ容量の小さなマシンでもコンパイラを利用可能ということでもある。また、オペレーティングシステムを高水準言語で素早く開発することが可能で、バロース B5000 や HP 3000 で実際にそのように開発された。UCSD p-System が初期の8ビットマイクロプロセッサを使ったメモリ容量の小さなシステムで動作できたのも、仮想スタックマシンをターゲットとしてコンパイルしたためである。
- コンパイラが単純ということは、コンパイラ最適化の最新技術の恩恵にあずかれないという欠点もある。スタックマシンでのコンパイラ最適化は不可能ではない。バックエンド部の最適化で劇的にコードの効率を向上させた例があり[2][3]、大域的な最適化でさらに性能向上させた例もある[4]。
- インタプリタの単純さ
- スタックマシンの命令セットには、直接ハードウェアで実装するのではなく、仮想機械でインタプリタ的に解釈することを意図したものもある。仮想スタックマシンのインタプリタは相対的に構築が容易である。これは、メモリアドレスとして基本的にスタックのトップだけを意識すればよいという性質に起因している。また命令の種類も相対的に少ない。
- プロセッサの状態数が少ない
- データスタックを持つマシンで必須となるレジスタは、スタックのトップのアドレスを保持するレジスタ（スタックポインタ）と、次の命令のアドレスを保持するレジスタ（命令ポインタ）だけである。このためコンテキストスイッチや割り込みの際にセーブすべき状態情報が小さい。
- 高速なオペランドアクセス
- レジスタマシンと異なりオペランドを指定する領域が命令内に存在しないため、命令の読み出し・デコードと並行して、その命令が使用するオペランドの読み出しを行うことが出来る。加えて、明示的なロード命令を用いない限り、スタック内のオペランドが使われる順序は、スタックトップから下方へ積まれている順序と一致する。このため、スタックトップから優先してレジスタファイルなどにキャッシュされた状態を保つだけで、オペランドの強力なプリフェッチが実現される。さらに、各命令のオペランドが取り出される場所はスタックトップ数個の範囲内に絞られるため、このスタックトップ数個をキャッシュする代わりに命令パイプライン内のフォアワーディング回路に流すことで、レジスタファイルへのアクセスを命令パイプラインの実行ステージ以前のステージから排除できる。このようにレジスタマシンと比較して命令パイプラインの長さを短く出来るため、より高い動作周波数、または、より少ない遅延スロットを実現できる。
- 仮想マシンの場合でも、この性質は有用である。ハードウェアでのフォアワーディング回路の代わりに、スタックトップをレジスタにキャッシュする実装が広く行われており、メモリロード遅延の影響が抑えられている。レジスタマシンを仮想マシンで実装する場合、多くのホストマシンでは実行時にレジスタを番号で参照することができないため、番号で参照するならメモリ配列を用いる方が単純かつ高速となる。また、仮想マシンの管理用にホストマシンのレジスタが消費されるため、ターゲットマシンのレジスタの全てを実装するにはホストマシンのレジスタが足りなくなる事もある。このため、ターゲットマシンのレジスタを実装するのにホストマシンのメモリ領域が使われる事が多い。
欠点
- メモリ参照が多い
- 業界には、一時変数や局所変数の操作でレジスタマシンよりもスタックマシンの方がデータキャッシュに頻繁にアクセスするという見方もある[5]。一方、それとは全く逆の主張もある[6]。ここでは、スタックマシンにおけるメモリアクセスパターンを理解する必要がある。
- スタックマシンでは一時変数がメモリに置かれることが多いのに対し、多数のレジスタを持つマシンでは一時変数はレジスタに保持され続ける。ただし、多数のレジスタがあるということは、割り込みやコンテキストスイッチでセーブ/リストアすべきデータが多いということも意味する。一時変数がメモリに置かれれば、データキャッシュへのアクセスは増えるが、その度合いはスタックのトップをどれだけレジスタ化しているかで変化するし、プロシージャコールが入れ子になる頻度や割り込み発生頻度によっても変わってくる。
- スタックのトップ部分をレジスタ化していない単純な実装では、レジスタマシンよりも性能が低くなる。例えば X+1 という式はスタックマシンでは 'Load X; Load 1; Add' という3命令になる。これは、「Xをロードしてスタック（メモリ）にプッシュ。1をスタックにプッシュ。スタックから2つの値をポップしてそれらを加算し、結果をスタックにプッシュ」という意味であり、5回データキャッシュにアクセスすることになる。スタックのトップがレジスタ化されていても、最悪ケースではデータキャッシュのアクセス回数は減らない。レジスタマシンでは最適化によってなるべく値をレジスタに保持しようとするので、最初にXをロードするだけで済む。一方で、レジスタマシンはプロシージャコールの入れ子で一時変数として使っているレジスタの内容を一斉にメモリにセーブする必要が生じる。
- 共通部分式除去のコストが高い
- レジスタマシンでは、同じ式の値を複数回使用する場合に、それを1回だけ計算して結果をレジスタに保持しておき、再利用することができる。スタックマシンで同じことをしようとすると、2つの方法が考えられる。1つは、共通部分式の計算結果をメモリ上の一時変数にセーブする方法である。しかし、これは共通部分式が単なるメモリ上の変数の参照などだった場合、全く最適化になっておらず、ある程度複雑な式でないと効果を生じない。そしてプログラマは複雑な式の結果をソースコード上で局所変数に格納し、何度も同じ式を書くことはしないのが一般的である。2つめは、共通部分式の計算結果をスタック上に残し、それを必要なだけ複製して利用する方法である。これは、"DUP"、"ROT"、"OVER" といったスタック操作を行ってもスタックがそれほど深くならない場合には効果的である。仮想スタックマシンの中には、"PICK" という命令でスタック内の指定した位置の値をスタックトップに複製する機能を持つものもある。Forthなどで書かれたプログラムはこのような技法を多用していることが多く、結果としてレジスタマシン並みの性能を達成している[7][6]。しかし、スタック・スケジューリングの最適化アルゴリズムは一般に知られておらず、スタックマシンを意識しない通常の言語でそのような最適化を行うことは難しい。結果としてスタックマシン向けコンパイラでは共通部分式除去などの最適化は行われていない。
- コード順序の厳密性
- 最近のコンピュータでは、データをフェッチするのにかかる時間は、ALUで演算を行うのにかかる時間よりも長い。したがって、メモリ上のデータが実際に必要になるよりも十分前にフェッチを開始すれば、命令パイプラインをストールさせることなく高速に処理を継続できる。アウト・オブ・オーダー実行方式では、複数の命令をプロセッサが調べてそのような動作をしている。アウト・オブ・オーダー方式でなくともレジスタマシンであれば、コンパイラが賢ければそのようなコードを生成することができる[5]。この命令スケジューリングには使っていないレジスタがなければならない。従って純粋なスタックマシンにはこのような命令の並べ替えは不可能である。例えば A - B という式があるとき、スタックマシンではAとBをロードしてスタックにプッシュしてから即座に減算を行う。途中に別の命令を挟もうとしても、スタックマシンの命令は基本的にスタックをいじるので、ほとんど何もできない。スタックマシンでは、メモリからのロード遅延を隠蔽できるほど深いパイプラインでアウト・オブ・オーダー実行を行うか、ハードウェアマルチスレッディングでスレッドを切り換えてロード遅延を隠蔽するしかない。ユニシスのA9システムでは後者の方式を実装している[8]。最近では計算負荷の並列性が高まっており、この欠点は過去のものとなりつつある。
- スタックトップの内容を追跡する事によって、この欠点は克服されている。例えば、スタックトップ2個がレジスタ化されているインタプリタで"A B C - /"という式(逆ポーランド記法の場合。通常記法での"A / (B - C)"に当たる。)を計算するとき、"Aのロード"と"B C - の演算"の両方とも、結果がレジスタに格納される。レジスタ・リネーミングを行う物理プロセッサでは、レジスタ間演算の依存関係を認識してアウト・オブ・オーダー実行が行われる。このため、"Aのロード"と"B C - の演算"に依存関係がなく並べ替えが可能であることを物理プロセッサは認識し、"Aのロード"の途中で"B C - の演算"を挟む。Mopsをx86_64(レジスタマシン)向けにコンパイルするiMopsでは、コンパイル時に追跡可能なスタックをノードとするノードグラフを対象にレジスタ割り当てを行い、プロセッサによる命令並べ替えを助ける。物理スタックマシンについても、レジスタマシンで論理レジスタをレジスタ・リネーミングするのと同様に、スタックなどのメモリ領域をリネーミングすることでTomasuloのアルゴリズムの実装が可能だと言われている[9]。
- 高速レジスタを隠蔽する
- 多くのスタックマシンは、スタックのトップN個の場所に対応するレジスタファイルを備えており、ロード命令やALU命令はその最上位近辺を対象とし、プッシュによってあふれた最下位のレジスタの内容はメモリ上のスタックに自動的に転送される。このため命令自体を小さくでき、命令のデコーダも小さくできる。しかし、命令が明示的にレジスタファイル内の個々のレジスタを指定できれば、コンパイラでレジスタの利用効率を向上させる最適化が可能となる。
- HP 3000 やタンデムコンピューターズの T/16 はスタックマシンだが、RISCマシンへ移行する際にスタックマシンのコード列を等価なRISCのコード列に変換するトランスレータを用意した[10][11]。この際に局所的最適化を施して、スタックアーキテクチャのオーバーヘッドの多くを除去している。例えばアドレス計算の反復を、使ってないレジスタに保持することで1回にしている。変換後のコードにはマシン間のアーキテクチャの違いからエミュレーションによるオーバーヘッドが多々含まれていたが、スタックマシンでの実行効率とほぼ同程度の効率を達成している。そして、ソースコードをRISCマシン向けの最適化コンパイラで再コンパイルした場合、効率は倍化している。このことから、スタックマシンのアーキテクチャと非最適化コンパイラは、そのハードウェアの能力の半分を浪費していたと見られる。
- レジスタファイルは、データキャッシュ経由のメモリ参照に比べると高帯域幅で低レイテンシである。ALUでの演算の場合、2つのレジスタを入力として1つのレジスタに演算結果を格納するまでを1サイクル以下で実行できる。一方データキャッシュは1サイクルに1回のアクセスしかできないため、同じことをしようとすると最低でも3サイクルかかることになり、実際にはそれぞれのアクセスが1サイクルで完了することはない。
- 仮想スタックマシンの問題点
- 仮想スタックマシン向けにプログラムをコンパイルすると、レジスタマシン向けよりも（コードサイズは小さくとも）命令数が多くなる。仮想スタックマシンを実装したインタプリタは、命令コードに従って分岐して対応する命令コードの処理を行う。また、スレッデッドコードで実装した場合も頻繁に分岐を繰り返すことになる。インタプリタの分岐先は命令コードの種類という膨大な数であり、その様な分岐を効率よく行うため、間接分岐命令が使われる。ところが初期の分岐予測機構では、間接分岐命令への対応が欠けている。このため、仮想スタックマシンの命令をデコードして実行するたびに、ホストマシンのパイプラインは誤った分岐先を投機実行し、修正のためリスタートすることになる。個々の命令が単純で命令数が多くなるため、そのような状況はスタックマシン以外の仮想機械よりも仮想スタックマシンで発生しやすいと言われている[12][13]。AndroidのDalvik仮想マシンはJavaを実行するが、本来のJava仮想マシンが8ビットのスタックマシンなのに対して、16ビットのレジスタマシンとなっている。これにより命令数を少なくし、命令コードディスパッチでのストールを低減している。算術命令は4ビット（以上）のオペランドを使って直接局所変数をフェッチまたはストアすることができる。
- ただし、分岐予測が成功している場合、パイプラインのリスタートは生じず、予測と実行後の分岐先を比較するALU演算程度まで分岐命令のコストは低下する。Java仮想マシンインタプリタの普及に伴い、インタプリタにも対応できる分岐予測器を積んだプロセッサが普及しており[14]、この問題でのレジスタマシンとスタックマシンとの差は縮まっている。
ハイブリッド方式
純粋なスタックマシンは、構造を持つデータオブジェクトの複数のフィールドにアクセスするのが不得意である。スタックマシンでは、オブジェクトのベースアドレスとフィールドのオフセットからアドレスを計算しなおして、ポインタをスタック上に置きなおす必要がある。一般的な対処方法としては、レジスタマシンの一部機能をスタックマシンに取り入れ、アドレス格納用にソフトウェアから見えるレジスタファイルを用意し、レジスタマシン風の命令でロードや単純なアドレス計算を行う。なお、レジスタファイルを汎用なものにするとスタックマシンである積極的な理由がなくなってしまう。
もう1つの一般的なハイブリッド方式として、レジスタマシンのアーキテクチャを出発点とし、スタックマシンでのプッシュおよびポップをエミュレートする操作を追加する方式がある。この方式をポピュラーなものにしたのは、DECのPDP-11ミニコンピュータである。これがVAXに受け継がれ、MC6800やMC68000といったマイクロプロセッサにも採用された。これにより初期のコンパイラでスタックを簡単に扱えるようになった。また、スタックインタプリタまたはスレッデッドコードを使って仮想機械を効率的にサポートする。ただし、これによってレジスタマシンのコードが純粋なスタックマシンほどコンパクトになるわけではない。このようなハイブリッド方式のマシンで、スタックマシンのように頻繁にプッシュやポップを行うと性能は悪くなる。スタック操作はプロシージャコールの際にのみ行う方がよく、当然ながらメモリ参照せずにレジスタのみで処理するのが最善である。
第2世代スタックマシンと呼ばれるものは、データスタックからメモリアドレッシングの処理を肩代わりするアドレスレジスタ群を備えている。例えば、MuP21は "A" というレジスタを持っており、もっと最近の GreenArrays のプロセッサは A と B という2つのレジスタを持っている[6]。
x86ファミリは基本的にレジスタ指向の命令セットだが、初期は外付けされ、後には内蔵・一体化された、浮動小数点関係のx87命令と浮動小数点レジスタは、スタック（マシン）指向である。これも一種のハイブリッドと言えよう。これは初期（1980年代）に、命令空間やチップ面積を節約する必要があったためである。現代の64ビット化されたx86であるx64では、（互換のために従来のFPUも残されているが）通常使用されるSSEの浮動小数点関係の命令も全てレジスタ指向の命令（レジスタ指向のSIMD命令）となっている。
実用化されたスタックマシン
ハードウェアで直接実行されるスタックマシン型命令セットの例を挙げる。
- GreenArrays, Inc. の GA144 マルチコンピュータチップ
- バロース B5000 アーキテクチャ（1961年から）
- English Electric KDF9 (1964[要出典] : 出荷開始が1963年とする文献[1][15])。レジスタで16段のスタックを実装。
- Collins Radio のミニコンピュータ Collins Adaptive Processing System (CAPS, 1969) と Rockwell Collins の Advanced Architecture Microprocessor (AAMP, 1981)[16]
- UCSD Pascal p-machine をハードウェアで実装したもの（Pascal MicroEngineなど）
- MU5と ICL 2900 シリーズ。スタックマシンとアキュムレータマシンのハイブリッド方式。アキュムレータはスタックトップの値をバッファする。
- タンデムコンピューターズ T/16
- HP 3000 （PA-RISC ではなく、それ以前の CISC）
- Atmel MARC4 マイクロコントローラ[17]
- Forth言語を実装したチップ[18]。RTX2000、F21[19]、PSC1000[20]など。
- Bernd Paysan による4つのスタックを持つマシンの提案[21]
- "Ignite" スタックマシン。チャールズ・ムーアがアーキテクチャを設計。
- Saab Ericsson Space の放射線耐性を強化したマイクロプロセッサ Thor[22]
- インモス トランスピュータ
仮想スタックマシン
ソフトウェアで解釈される仮想スタックマシンの例を挙げる。
古典
- SECDマシン
- UCSD Pascal p-machine
- サン・マイクロシステムズの Sun Ray スマートカードの定義作成のための SwapDrop 言語
- Forth言語処理系。特にスレッデッドコードで実装されているもの。
現代のもの
- Java仮想マシン命令セット
- .NET 環境における共通中間言語命令セットおよびその仮想機械である VES（仮想実行システム）
- CPython バイトコードインタプリタ
- WebAssembly[23]
- アドビのPostScript
→詳細は「コールスタック」を参照
現代のほとんどのコンピュータ（命令セットを問わない）とほとんどのコンパイラは、メモリ上のコールスタックを局所変数の格納場所およびサブルーチンからの復帰のための情報格納に使っている。サブルーチンコールのたびに「スタックフレーム」をコールスタック上に作り、そのサブルーチンから呼び出し側に復帰するまで対応するスタックフレームが維持される。コールスタックを特別なアドレスレジスタなどを使ってハードウェアで管理する場合もある。あるいは、コンパイラの呼出規約によって特定の汎用レジスタをコールスタック処理に使う場合もある。
一般にコンピュータは、大域変数とその時点で実行中のプロシージャまたは関数の局所変数への効率的アクセス手段を提供する。一般に呼び出し側のプロシージャまたは関数のスタックフレームを遡ってアクセスする必要性はほとんどなく、ハードウェアが直接そのような手段を提供することもない。必要ならば、スタックフレーム内にあるフレームポインタで遡ることもできる。
バロース B5000 ではハードウェアでスタックフレームを遡る手段を提供しているが、これは動的な入れ子構造ではなく、プログラムの静的な入れ子構造（変数のスコープ）を辿るものである。その後このような機能をハードウェアで実装した例はない。ニクラウス・ヴィルトは CDC 6000 シリーズ向けにPascalコンパイラを開発した際、フレームポインタを配列に格納して常に更新するよりも、コールスタック上のフレームポインタを遡ってたどった方が全体として高速だということを発見した。この方式だと、遡って参照することのないC言語などのプログラミング言語でも、余計なオーバーヘッドが発生しない。
バロース B5000 では、タスクまたはスレッドの入れ子もサポートしている。あるタスクとそのタスクを作ったタスクは、タスク作成時点のスタックフレームを共有するが、作成した側の次のフレームや作成されたタスク自身のフレームは共有されない。そのため西部劇でよく見るようなサボテンのようなスタック構造になる。各タスクは自身のスタックとフレームを保持するメモリセグメントを持つ。そのスタックのベースは作成した側のスタックの途中とリンクされている。一般的なフラットなアドレス空間を持つマシンでは、あるタスクのスタックとそれを作成した側のスタックは1つのヒープ内の別々のヒープオブジェクトになる。
プログラミング言語によっては、外側のスコープのデータ環境が常に入れ子になっているわけではない。そのような言語では、1つのスタックにスタックフレームを積んでいくのではなく、別個のヒープオブジェクトとしてプロシージャの「アクティベーション・レコード」を編成する。
Forthのような単純な言語では、局所変数やパラメータの名前がなく、スタックフレームにはリターンアドレス以外に何も必要としない。そのため、リターンスタックにはフレームが存在せず、単にリターンアドレスが格納される。リターンスタックとデータスタックは分離しており、プロシージャの呼び出しと復帰は高速に行われる。
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
