スタックについて

関数呼び出しのためには、呼び出された関数の中だけで用いられる変数を格納 しなくてはなりません。また、その関数呼び出しが終了したときに、プログラ ムカウンタをどこに戻せばばいいかということも記憶しておかなくてはなりま せん。これらの情報は、関数呼び出しの中だけで必要であり、その関数呼び出 しの中でさらに他の関数を呼び出すと、古い関数呼び出しのための情報を保持 したまま、新しい関数呼び出しのためのものも記憶する必要が生じます。特に、 再帰的な関数の呼び出しを行うと、関数の呼び出しの中でまた同じ関数が呼び 出されることになります。そのためには、これらの情報を記憶する領域を 関数ごとに用意する訳にはいかず、呼び出しの度に、新しく用意する必要が あります。

それを実現するのがスタックです。コンピュータでプログラムの実行のために 使われるメモリ領域は、プログラム領域、データ領域、スタック領域の３つに 分けられます。スタック領域上には、関数呼び出しの度に、スタックフレーム という領域がとられて、そこに、その関数の中で使われるローカル変数の値と、 その関数呼び出しが終わった時の戻り先（戻り番地）が記憶されます。CPU に は、ベースレジスタというレジスタがあって、それが、現在のスタックフレー ムの場所を指し示しています。スタック上に置かれるローカル変数は、呼び出 しのたびに、スタックフレームがとられる場所が変わるため、そのアドレスを マシン語の命令の中に直接指定することができません。そこで、マシン語の命 令の中では、このベースレジスタからどれだけ先かという差分が指定されてます。 これを、ベースレジスタに対する相対アドレッシングといいます。

このプログラムは、スタックの機能を追加したコンピュータ・シミュレータで す。マシン語の1命令を１バイトにおさめるために、実際のコンピュータと多少 異なったところがありますが、マシン語の関数呼び出しの概念は、これで十分 理解できます。

マシン語について

命令が１６個でおさまらないので、引数を取らない命令は上位４ビットで示す 番号を一つにまとめて、下位４ビットでそのどれかを示すようになってます。

ＣＰＵの中には、ベースレジスタとスタックポインタと呼ばれる２つのレジス タが追加されています。スタック上の値へのアクセス（相対アドレッシング） は、アセンブラでは、Ln (n = 0,1,2,3) という形で表記します。これで、ベー スレジスタの値に n を加えたアドレスへのアクセスになります。

Ln は、マシン語で表現するために、間接アドレッシングでアクセスできるのは、 データ領域の最初の４つの番地だけに制限して、あいたスペースを相対アドレッ シングに使用しています。つまり、下位４ビットが 0 で始まるなら残り３ビッ トで直接アドレッシング、10 で始まるなら残り２ビットで間接アドレッシング、 11 で始まるなら、残り２ビットで相対アドレッシングです。

また、push 命令によって、レジスタの値を次のスタックフレームの L0, L1, ... の位置に順に置くことができます。push 命令によって次にどこのアドレ スに置かれるかは、スタックポインタが記憶しています。すなわち、push によっ て、スタックポインタの値は１増えます。

call 命令によって、現在のプログラムカウンタの値が次のスタックフレームの 先頭に記憶され、その次のスタック上のアドレスがベースレジスタに設定され ます。また、スタックポインタは、さらにその次の関数呼び出しのためのフレー ムのローカル変数の置き場所（すなわち、新しいベースレジスタ＋５）に設定 されます。

return 命令によって、return の引数の値が返り値としてレジスタにとられ、 ベースレジスタの１つ前のアドレスの値がプログラムカウンタに設定され、ベー スレジスタが５つ戻され、そこから５つ先にスタックポインタが設定されます。

Hideki Tsuiki,
tsuiki@i.h.kyoto-u.ac.jp