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

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

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

スタックの基礎

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

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

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

関数の呼び出し

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

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

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

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

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

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

自動変数

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

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

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

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

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

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

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

フレームポインタ

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

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

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

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

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

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

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

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

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

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