コールスタック

コールスタックまたは呼び出しスタック（）とは、プログラムで実行中のサブルーチン（関数）に関する情報を格納するスタックである。実行中のサブルーチンとは、呼び出されたもののまだ処理が完了していないサブルーチンのことを指す。実行スタック (execution stack)、制御スタック (control stack)、関数スタック (function stack) などとも呼ばれる。なお文脈によっては、短縮して単にスタックともいう。
概要.
コールスタックを使う目的はいくつかあるが、主たる目的はサブルーチンの処理を完了して制御を戻す（呼び出し側に戻る）ときに、どこに戻ればよいかを記憶しておくことである。
コールスタックはスタックとして構成されているので、呼び出し側はリターンアドレスをスタックに "push" し、呼び出されたサブルーチンが完了したときにリターンアドレスをコールスタックから "pop" する（そしてそのアドレスに制御を戻す）。呼び出されたサブルーチンがさらに別のサブルーチンを呼び出す場合も、リターンアドレスをコールスタックに push し、プログラムに書かれている通りに情報をスタックに積んだり下ろしたりする。あるサブルーチンに関する情報をコールスタックに載せることをワインド (巻き上げ, winding)、逆にそれを削除することをアンワインド (巻き戻し, unwinding) と呼ぶ。また、サブルーチンの呼び出しごとにコールスタックに格納するひとまとまりの情報の集合をスタックフレーム (stack frame) または単にフレームと呼ぶ。
なお、コールスタックに割り当てられている領域を使い切ると「スタックオーバーフロー」と呼ばれる実行時エラーが発生する。スタックオーバーフローが発生したときの動作はプログラミング言語や実行環境によって異なるが、通例プログラムの異常終了といった未定義動作を引き起こし、回復不可能であることが多い。
1つの実行中のプログラム（より正確に言えばスレッド）には、1つのコールスタックが対応して存在する。シグナル処理や協調的マルチタスク処理で追加のスタックを使う場合もあるが、通常使用中のコールスタックは常に1つなので、これを単に「（そのタスクの）スタック」と呼ぶことがある。
低水準言語（アセンブリ言語）の多くでは、プログラマが明示的にスタックを操作する必要がある。一方、高水準言語からはコールスタックは透過的である。つまりコールスタックの存在を意識することなく、呼び出し階層構造によって実現される上位概念としてのプログラムロジックにのみ集中できるということである。コールスタックの詳細はプログラマからは見えず、サブルーチン（関数）のリストや、引数あるいはローカル変数といった形でスタックから切り出された部分領域だけにアクセス可能で、スタックを構成しているメモリ全体にアクセスすることはできない。
各プログラミング言語におけるスタックの詳細は、コンパイラ、オペレーティングシステム (OS)、命令セットなどに依存する。
いずれにせよ、言語環境を問わず、ソフトウェアを正常動作させるにはコールスタックを正しく保つことは重要である。コールスタックの容量は、デスクトップOS環境であっても既定で数MiB程度しかなく、組み込み環境ではさらに制限が厳しい。高水準言語では普段コールスタックの存在を意識しないで済むがゆえに、ヒープではなくスタック上に巨大な配列を確保して容量を使い切ってしまい、スタックオーバーフローを発生させてしまうといった初歩的な間違いを犯すこともある。
具体例.
コールスタックが関係する具体例として、次の擬似コードを挙げる。
 subroutine DrawSquare(Point p1, Point p2, Point p3, Point p4)
 ... 略 ...
 DrawLine(p1, p2);
 DrawLine(p2, p3);
 DrawLine(p3, p4);
 DrawLine(p4, p1);
 ... 略 ...
上の疑似高水準言語のコードでは、サブルーチンcodice_1内の4ヶ所から、直線を描画するサブルーチンcodice_2を呼び出すとしたとき、codice_2は4ヶ所のうちのどこに戻ればよいかを知る必要がある。一般にcodice_1のコード内でcodice_2を呼び出しているそれぞれの箇所で、呼び出し処理の次の命令のアドレス（これをリターンアドレスと呼ぶ）をコールスタックに格納することでこれを実現する。
コールスタックの機能.
前述のように、コールスタックの第一の用途は以下の通りである。
言語、オペレーティングシステム、ハードウェア環境に依存するが、コールスタックはそれ以外の機能も持つことがある。そのような機能として以下のものがある。
典型的なコールスタックはリターンアドレス、局所データ、引数を格納する（これを「コールフレーム」と呼ぶ）。環境によってはコールスタックの機能に差異がある。例えばFORTH言語では、コールスタックにはリターンアドレスと局所変数のみが格納され（これをリターンスタックと呼ぶ）、引数は別のデータスタックに格納される。多くのFORTHの実装では浮動小数点数の引数を格納するための第三のスタックが存在する。
構造.
コールスタックはスタックフレームから構成される（アクティベーションレコードとも呼ばれる）。スタックフレームはマシン依存のデータ構造であり、サブルーチンの状態情報が格納される。各スタックフレームは完了していないサブルーチン呼び出しに対応する。例えば、codice_1から呼び出されたcodice_2を現在実行中としたとき、コールスタックのトップ部分は下図のようになる。
スタックトップのスタックフレームは現在実行中のルーチンのためのものである。最も典型的な手法では、スタックフレームには次の情報が格納されている。
フレーム内のメモリ領域はスタックポインタと呼ばれるレジスタを使ってアクセスされることが多い。スタックポインタはスタックのトップを指している。別の方法として、スタックポインタとは別のレジスタ（フレームポインタと呼ばれることが多い）を使うこともある。フレームポインタはフレームの中の決まった場所を指していて、例えばリターンアドレスが格納されている位置を指している。
スタックフレームは必ずしも同じサイズではない。サブルーチン毎に引数の個数も違うので、スタックフレームのサイズも異なる。ただし、同じサブルーチンを呼び出したときのスタックフレームは一般に同じサイズとなる。同様に局所変数領域もサブルーチンが違うとサイズが変わってくる。実際、言語によってはスタック上に動的にメモリを確保する機能を持っているので、同じサブルーチンを呼び出してもフレームサイズは変わってくるし、そのサイズはコンパイル時にはわからない。そのような場合、スタックポインタではなくフレームポインタでアクセスする必要が生じる。というのは、スタックポインタからリターンアドレス格納位置までのオフセットがコンパイル時に判明しないからである。
多くのシステムでは、スタックフレーム内に前のフレームポインタレジスタの値を格納する場所がある。つまり呼び出し側ルーチンを実行していたときに使っていたフレームポインタの値である。例えば、上図のcodice_2のスタックフレーム内にcodice_1が使っているフレームポインタの値を格納する場所があるということになる。その値はサブルーチン呼び出し時に格納され、復帰時に戻される。そのようなフィールドがスタックフレーム内の所定の位置にあると、コールスタックに積まれているスタックフレーム群を（さかのぼって）辿っていくことが可能となる。
場合によっては、スタックフレームはオーバーラップしていると見なすこともできる。オーバーラップしているのは、呼び出し側から呼び出されたルーチンに渡される引数の部分である。環境によっては呼び出し側はスタックに引数をpushして自身のスタックフレームを拡張し、その後に呼び出しを行う。また別の環境では、各サブルーチンは自身が呼び出すかもしれない別のサブルーチンへの引数の領域を予めスタックフレーム内に確保していることがある。この領域は outgoing arguments area あるいは callout area と呼ばれる。この手法ではコンパイラが呼び出す可能性のあるサブルーチンのうち最大の引数領域を必要とするものを予め求めて領域サイズを決定する。
使用法.
呼び出し側処理.
通常、サブルーチンを呼び出す側でのコールスタック処理は最小限になっている。呼び出すコードがあちこちに存在することを考慮すれば、こうすることでコードの増大を抑えることができる。実際の引数の値は呼び出し毎に固有なので呼び出し側で評価され、呼出規約に従ってスタックにpushされるかレジスタに置かれる。「Branch and Link」のような実際の呼び出し命令が制御をターゲットのサブルーチンに転送するために実行される。
呼ばれた側の処理.
呼ばれたサブルーチンでは、最初にと呼ばれるコードを実行する。そこで実際のコードを実行する前に行わなければならない細々とした処理を行う。
プロローグでは、一般に呼び出し命令が所定のレジスタに置いたリターンアドレスをコールスタックにpushする。同様に現在のスタックポインタかフレームポインタ（あるいは両方）をpushする。命令セットアーキテクチャによってはこれらが呼び出し命令の一部として実行され、そのような環境ではプロローグですべきことは無い。
フレームポインタを使っている場合、プロローグではフレームポインタに新たな値をセットする（スタックポインタの値を活用する）。局所変数の領域は必要に応じて徐々にスタックポインタを変化させて確保していく。
FORTH言語ではコールスタック（リターンスタック）を明示的にワインドすることができる。Scheme言語では「動的ワインド (dynamic wind)」という機能があり、スタック上に特殊なフレームをワインドすることができる。
復帰処理.
サブルーチンから復帰することができる状態になると、プロローグの逆のエピローグ処理が行われる。これは一般的には保存されていたレジスタの値（フレームポインタなど）をスタックフレームからリストアし、スタックポインタの値を変更してスタックフレーム全体をpopし、最後にリターンアドレスに分岐する命令を実行する。多くの呼出規約ではエピローグ処理でpopする範囲に元々の引数も含まれる。その場合、呼び出した側に戻ったときにすべきことは何もない。呼出規約によっては、引数部分のpopを呼び出し側の責任で行うものがある。
アンワインド.
呼び出された関数から復帰するとスタックのトップにあったフレームがpopされ、戻り値が残される。
Pascalなどの言語は関数の入れ子を越えた広域のgoto文をサポートしており、呼び出し側関数に制御を移すことができる。このとき、スタックのアンワインドを行って、goto文の戻り先の関数に対応したスタックフレームまで戻す必要がある。このような制御の転送は一般にエラー処理にのみ使われる。
スタックは例外処理の際にもアンワインドされなければならない。例外をサポートするためには、スタックフレームにさらに例外ハンドラを示すエントリが必要となる。例外がスローされると、スタックはその例外を処理できる例外ハンドラが見つかるところまでアンワインドされる。Common Lispではスタックがアンワインドされたときに起きることを制御するcodice_10という特殊なマクロがある。
継続を適用する場合、スタックは一度アンワインドされ、再度ワインドされて実行を継続する。継続を実装する方法はこれだけではなく、明示的に複数のスタックを用意して継続するアプリケーションが単にそのスタックを起動して渡すべき値をワインドする。
コールスタックとソフトウェアテスト.
2006年、コールスタックを使ったこれまでとは全く異なる技法が発表された。それはコールスタックを使った test suite reduction と呼ばれる技法である。大まかに言えば、実行時のコールスタックが同じになるテストケースは等価だとみなしてテスト件数を減らしつつ、テストスイート全体の問題検出能力を維持するという考え方である。
性能解析.
無作為にコールスタックの標本を採取することで、プログラムの性能最適化に利用することができる。コールスタック上によく現れるサブルーチンは頻繁に呼び出されるか1回の実行に時間がかかっていると想定でき、その呼び出し回数を減らしたり、1回の実行にかかる時間を短縮することで大きな効果が期待できる。詳しくは性能解析を参照。
セキュリティ.
コード（リターンアドレス）とデータ（引数、戻り値、局所変数）がコールスタックに混在していることはセキュリティ上危険である。詳しくはバッファオーバーランおよびスタックを参照されたい。