第4回 スタック

スタックというのは、後入れ先出しのデータ構造のことですが、ここで解説するのは、その中でも、CPU やコンパイラが管理しているスタックのことです。多くのCPUでは、スタックを実現するための機能がハード的に備わっています。また、RISC と呼ばれる種類に属している CPU では、スタック専用のハードウェアがないことが多いのですが、その場合は、コンパイラによってソフト的に同じ機能を実現しています。

スタックが具体的にどのように記述されているかはともかく、C 言語で記述されたプログラムを動作させるには、スタックの仕組みが不可欠です*1。これは、C 言語以外の大多数のプログラム言語についても同じことがいえます*2


*1 標準規格ではスタックについてはまったく触れられていませんが、現実的にはスタックなしで実行処理系を作ることはまず無理です。
*2 スクリプト言語のようなインタプリタの場合、スタックはソフト的に実現されている場合があります。

スタックの基礎

これから CPU やコンパイラが管理しているスタックについて解説するわけですが、スタックというデータ構造がわからないと話が進みません。そこで、簡単なプログラム片を使って、スタックの基礎について解説してみたいと思います。

int stack[STACKSIZE];
int *sp = &stack[STACKSIZE];

void push(int value)
{
  *--sp = value;
}

int pop(void)
{
  return *sp++;
}

上のコードは、スタックを理解するためのコード片です。CPU が管理しているスタックなどはハード的なものですし、RISC などで、コンパイラが作り出している場合はアセンブリ言語のコードになるわけですが、ここでは概念を理解していただくためにC言語で記述してみました。

スタックには、データを格納するための領域(上のコードでは配列stack)があり、スタックポインタ(変数 sp)が現在の操作位置を示します。そして、スタックへの操作は、データを格納するための push と、データを取り出すための pop の 2 種類があります。スタックの操作は push または pop を用いて行うことになります。

関数の呼び出し

それでは、C 言語で記述されたプログラムを動作させるために、実際にスタックがどのように使われているかを見ていきたいと思います。まずは、スタックを使う状況の中でも、もっとも典型的である、関数の呼び出しについてです。

ここでは、話を簡単にするために、int 型の引数をひとつだけ持ち、返却値を持たない、関数 func を考えることにします。

void func(int arg);

そして、この関数を次のように呼び出すことにします。

func(1234);

上のような C 言語のコードがあった場合、コンパイラは、まず実引数 1234 をスタックに push し、次に、関数から戻るときに分岐すべきアドレス(戻り先アドレス)をスタックにpushし、最後に func の先頭アドレスに分岐します。擬似プログラムで書くと、

push(1234);
push(戻り先アドレス);
goto func;

というイメージになります。そして、func からリターンするときは、pop 操作によって戻り先アドレスを取り出し、そのアドレスへ分岐した後、スタックポインタの位置を元に戻すために、1 回 pop を行います(実引数をスタックから取り除くことになります)。擬似プログラムでは、

ra = pop();  /* ra == 戻り先アドレス */
goto ra;

戻り先アドレス:
pop();

となります。このように、スタックを使うことで、関数の中からまた別の関数を呼び出すことが可能になります。関数の呼び出しが何段階になっても、スタックの領域があふれない限りは問題なく動作します。なお、再帰呼び出しなどでよくありますが、あまりにも関数の呼び出し階層が深くなると、そのうちスタックの領域が足りなくなって、動作がおかしくなってしまいます。

自動変数

関数の中で宣言された変数は、(extern や static などの)記憶クラス指定子を付けない限り、自動記憶域期間を持ちます。ここでは、そのような変数(正確にはオブジェクト)のことを自動変数と呼ぶことにします。

実は自動変数も、大多数の処理系ではスタックを利用しています。しかし、スタックは本来 push と pop によって操作しなければならないのですが、自動変数を実現する場合は、ちょっと反則気味な手法がとられています。

というのも、自動変数にアクセスするたびに、push と pop を繰り返すと、変数の管理も大変ですし、そのためのワーク領域としてのメモリが必要になりますし、実行効率も悪くなります。そのため、自動変数へのアクセスには、push や pop を使わずに、スタックポインタからの相対位置などを用いて、直接アクセスするようになっていることがほとんどです。

具体的な例を挙げて解説することにしましょう。関数の中で、a, b, c という int 型の変数を 3 つ宣言する場合について考えてみます。

int a;
int b;
int c;

この場合、a, b, c という三つの変数を割り付けるために 3 回 push を行ってもよいのですが、普通はそうではなく、スタックポインタから直接3を引く場合が多いようです。そして、a, b, c へのアクセスには、sp[0~2] を使って行うわけです。上記の宣言のあと、

a = 123;
b = a + 1;
c = b * 2;

のように、a, b, cを操作する場合、擬似プログラムでは、

sp -= 3;          /* a, b, cを割り付け */
sp[0] = 123;      /* a = 123 */
sp[1] = sp[0] + 1; /* b = a + 1 */
sp[2] = sp[1] * 2; /* c = b * 2 */

のようになります。そして、関数からリターンするときには、sp += 3 によってスタックポインタを元に戻してやれば、自動変数を解放することができます。

フレームポインタ

先ほどは、自動変数へのアクセスはスタックポインタ(sp)からの相対位置を用いる例を取り上げました。しかし、多くの処理系では、自動変数や仮引数へのアクセスのために、フレームポインタという概念を取り入れています。

スタックポインタからの相対位置を使っていると、関数の中の複合文で自動変数を宣言された場合など、その都度スタックポインタの値が変わることになるので、同じ変数を表すための sp の添え字が必ずしも一定になるわけではなく、管理が面倒になりますし、何よりデバッグが大変になります。

そのため、関数が呼び出された直後のスタックポインタの値をフレームポインタに保持しておき、自動変数はフレームポインタからの相対位置を使うわけです。フレームポインタをfpとすると、関数が呼び出された直後に、

push(fp);
fp = sp;

という擬似プログラムで表されるような操作が発生します。いったん fp を push しているのは、関数の中から別の関数を呼び出した場合でも、元の fp を破壊しないようにするためです。

そして、先ほどの自動変数a, b, cを使った処理を、フレームポインタを使った擬似プログラムで書き直すと、

sp -= 3;            /* a, b, cを割り付け */
fp[-1] = 123;      /* a = 123 */
fp[-2] = fp[-1] + 1; /* b = a + 1 */
fp[-3] = fp[-2] * 2; /* c = b * 2 */

のようになります。また、これが func(int arg) の中であれば、仮引数 arg にアクセスするには、

fp[-1] = fp[2];  /* a = arg: */

のようになります。もっとも、これは戻り先アドレスや fp が int 型のサイズに収まる場合の話であって、そうでなければ arg をアクセスするためのfpの添え字も変わってきます。

このように、フレームポインタを使用する場合、添え字がプラスであれば実引数を、マイナスであれば自動変数を指すことになります。もちろん、これらのルールは C 言語の規格で決まっているわけではないので、処理系ごとに異なるルールになっているかもしれませんが、大体こんなところだと考えてよいでしょう。

C 言語の解説書では、「スタック」という言葉が普通に使われていることも少なくないのですが、スタックそのものについての解説は案外少ないように思います。また、アセンブリ言語で開発経験がある方であれば、スタックはおなじみの存在なのですが、C コンパイラがどのようにスタックを利用しているかが分からなかったりします。

C 言語で実際に開発を行うには、スタックについての理解が不可欠です。確かに知らなくても何とか動くものは作れますが、不具合が起きたときの解析力などは、スタックを理解しているのとそうでないのとでは、雲泥の差があります。