トップ言語処理 > 7B.スタックマシン

7B.スタックマシン

1.スタックマシン

スタックマシン(stack machine)とは、メモリがスタックの形式になっている計算モデルを意味する。 スタックマシンを実装あるいはシミュレートしている実在のコンピュータもスタックマシンと呼ぶ。

スタックマシンは「0オペランド」命令セットのマシンである。 0オペランドマシンでは、命令は暗黙のうちにスタックにある値を使って演算を行い、結果をスタックのトップに置く。 また、メモリの任意の位置の読み書きをする "load" 命令や "store" 命令 (ただし、アドレスは明示的に指定せず、スタックのトップにある値をアドレスとして使用する) およびスタックのトップに値を積む "push" 命令がある。 。

スタックマシン(0オペランド命令セット)がアキュムレータマシン(1オペランド命令セット)や レジスタマシン(2オペランド命令セット、3オペランド命令セット)に比較して優れているのは、 命令形式がシンプルでサイズが小さいことである。

例えば、1と2を足す場合、

  1. 1をスタックに積む
  2. 2をスタックに積む
  3. スタックから2、1を取り出し、加算し、計算結果の3をスタックに積む
という操作を行う。

2.スタックマシンの命令セットの例

教育用コンパイラTiny C[2]におけるスタックマシンの命令コードを下に示す。

命令コード 説明
POP  stackから、1つpopする。
PUSHI n 整数nをpushする。
ADD stackの上2つをpopして足し算し、結果をpushする。
SUB stackの上2つをpopして引き算し、結果をpushする。
MUL stackの上2つをpopして乗算し、結果をpushする。
GT stackの上2つをpopして比較し、>なら1、それ以外は0をpushする。
LT stackの上2つをpopして比較し、<なら1、それ以外は0をpushする。
BEQ0 L stackからpopして、0だったら,ラベルLに分岐する。
LOADA n n番目の引数をpushする。
LOADL n n番目の局所変数をpushする。
STOREA n stackのtopの値をn番目の引数に格納する。
STOREL n stackのtopの値をn番目の局所に格納する。
JUMP L ラベルLにジャンプする。
CALL e 関数エントリeを関数呼び出しをする。
RET stackのtopの値を返り値として、関数呼び出しから帰る。
POPR n n個の値をpopして、関数から帰った値をpushする。
FRAME n n個の局所変数領域を確保する。
PRINTLN s sのformatで、printlnを実行する。
ENTRY e 関数の入口を示す。(擬似命令)
LABEL LラベルLを示す。(擬似命令)

2.制作演習におけるスタックマシン

IA-32アーキテクチャのようなレジスタマシンよりもスタックマシンの方がシンプルなため、 制作演習ではスタックマシン用の命令コードを生成する。 詳細は後述するが、上で紹介した Tiny C に比べれば、もっと多くの命令コードが使われる。

スタックマシンをハードウェアで実現する場合、 演算用レジスタの代りに演算専用の高速アクセスが可能なスタックが置かれるが、 ソフトウェアで実現する場合は、演算専用スタックは設けず、 関数コールで使われる主メモリ上のスタック領域を共用する方がシンプルである。

スタックマシンでもレジスタが皆無となるわけではなく、スタックポインタ(sp)とベースポインタ(bp)は使われる。

関数コールのしくみはレジスタマシンの場合とほぼ同じである。

IA-32では主記憶は byte mem[サイズ] であるが、演習スタックマシンでは double mem[1000000] としている。 double型のデータ幅は8バイトであるから、主記憶 8MB の仮想マシンとなる。 必要に応じて、サイズは変更してよい。

番地(アドレス)あるいはポインタの値は mem配列の添え字である。 従って、演習スタックマシンでは アドレスの値は 0 〜 999999 の整数である。

演習スタックマシンでは文字列の本体自体は mem配列上には置かない。 mem配列上にはOS管理下の文字列保管場所のアドレスを置く。32ビットOSでは32ビットの整数である。 特にその値自体については何も知らなくてよい。

ソースコードをコンパイルして得られた機械語命令コードは主記憶 byte mem[] 配列上に置かれるが、 演習スタックマシンでは Inst構造体配列に置かれる。

スタックポインタおよびベースポインタの値は mem配列の添え字に当たり、 プログラムカウンタpcの値はこの Inst配列の添え字に当たる。

2.1 関数コールのしくみ

C言語標準関数 func(引数1,引数2) をコールする場合、引数2,引数1をスタックに積んで、 プログラムカウンタの値をスタックに積む(下図参照)。 プログラムカウンタは通常次の命令を指している。 つまり、次の命令の番地を戻り番地としてスタックに積んでおくわけである。

次に名前管理表を検索して関数funcの先頭番地(Inst配列の添え字)を プログラムカウンタにセットする。 これによって、関数funcにジャンプする。

関数の入口ではまず現在のベースポインタの値をスタックにプッシュする(積む)。 そして bp = sp を実行する。 つまり、この時点におけるスタックポインタの値をベースポインタにセットする。 spの値はこの後変化するが、bpの値はこの関数を実行している間は変わらない。 関数の処理の途中で別の関数をコールすることがある。 別の関数の処理が終わって、また元の関数の処理に戻ったとき、bpの値を復元できるようにするために、 関数入口でのbpの値をスタックにセーブしているわけである。 (最初は何のためにbpをセーブしているか分かりにくいと思うが)

ローカル変数1、2は構文解析〜コード生成で旧BPの上に割り当てられている。

このため、旧bpをスタックに積んだあと、ローカル変数が二つとすると、 sp の値を -2 として、スタックポインタがローカル変数領域のトップを指すように変更する。 (図の場合、次にpushすると変数2のすぐ上に置かれる)

スタックは通常、push するときはまず sp の値から1を引き、そこに値を置く。 つまり、spはスタックのトップの位置を指しており、次の位置を指しているのではない。

名前管理表の address は bp からの相対アドレスである。 図に示したように、引数1の相対アドレスは 2、 ローカル変数1の相対アドレスは-1である。

以上で関数入口の処理を終わり、関数出口では、スタックから旧bpの値を取り出し、 bp にセットして、戻り番地を pc にセットする。 これによって、元の関数に戻る。

レジスタマシンではこれでよいが、 スタックマシンでは関数の戻り値をスタックのトップに置く必要があるため、少し操作がいる。

レジスタマシンでは関数の戻り値は axレジスタに置く。 スタックマシンでも演算用スタックを専用に持てば、 関数コールからの戻りの処理はレジスタマシンと同様になり、余計な操作はいらない。

2.2 配列のサポート

実用プログラムには配列が欠かせない。 制作演習では1次元配列のみ取り扱う。多次元配列については、考え方のみ説明する。

次のプログラム

void main() {
    int data[3];
    int n;
     // 以下省略
}
では、メモリ配置は次のようになる。 実際には、戻り番地の下にコマンドパラメータ(プログラム名を含む)、 その先頭アドレス、コマンドパラメータの数を積んでいる。

typedef struct _Name {
    int  type;                  // NM_FUNC: 関数、NM_VAR: 変数、...
    int  dataType;              // データ型
    char *name;                 // 変数名または関数名
    int  addrType, address;     // アドレスの種別, 相対アドレス
    int  size;                  // サイズ
    int  ptrs;			// []の数(配列次元数)+ *(ポインタ)の個数: 当面は 1 か 0
} Name;

参考文献

[1] スタックマシン(Wikipedia)
[2] スタックマシン (Tiny-C)