コールスタック
コールスタックはスタックフレームから構成される(アクティベーションレコードとも呼ばれる)。スタックフレームはマシン依存のデータ構造であり、サブルーチンの状態情報が格納される。各スタックフレームは完了していないサブルーチン呼び出しに対応する。例えば、DrawSquareから呼び出されたDrawLineを現在実行中としたとき、コールスタックのトップ部分は下図のようになる。
スタックトップのスタックフレームは現在実行中のルーチンのためのものである。最も典型的な手法では、スタックフレームには次の情報が格納されている。
そのルーチンの局所変数領域
呼び出し側に戻るためのリターンアドレス
そのルーチンに渡された引数
フレーム内のメモリ領域はスタックポインタと呼ばれるレジスタを使ってアクセスされることが多い。スタックポインタはスタックのトップを指している。別の方法として、スタックポインタとは別のレジスタ(フレームポインタと呼ばれることが多い)を使うこともある。フレームポインタはフレームの中の決まった場所を指していて、例えばリターンアドレスが格納されている位置を指している。
スタックフレームは必ずしも同じサイズではない。サブルーチン毎に引数の個数も違うので、スタックフレームのサイズも異なる。ただし、同じサブルーチンを呼び出したときのスタックフレームは一般に同じサイズとなる。同様に局所変数領域もサブルーチンが違うとサイズが変わってくる。実際、言語によってはスタック上に動的にメモリを確保する機能を持っているので、同じサブルーチンを呼び出してもフレームサイズは変わってくるし、そのサイズはコンパイル時にはわからない。