factorプログラム
factorプログラムは、再帰呼び出しを利用して階乗を計算するプログラムである。
debugger\factor フォルダのプロジェクトファイル prime.dsw をVisual C++ 開発環境で開く。([ファイル]メニューの[ワークスペースを開く]から factor.dsw を指定するか、エクスプローラから factor.dsw をダブルクリックする。)
factorプログラムのソースコードを以下に示す。
includeSrcWithFrame('src/factor/factor.c', 4, "", true, true); ?>
(factor プログラムの15〜19行目の部分は、この演習での処理を見やすくするための Visual C++ 処理系に依存するコードであるので、無視してかまわない。)
プロジェクトをロードしたのちに、プログラムのビルド、デバッガ上での実行を行う。
プログラムを実行すると、階乗を求める値の入力を促すプロンプトが表示されるので、任意の値を入力する。すると以下のようなダイアログが表示され、実行が中断される。
factorプログラムには、無効なメモリ領域にアクセスしてしまうというバグがあり、実行すると例外が発生する。デバッガを用いないで実行した場合、例外が発生したプログラムは強制終了されてしまうが、デバッガ上で実行した場合には、デバッガがこの例外をトラップする。ダイアログの[OK]ボタンを押すと、ソースコード中の例外の発生位置を表示して一時停止する。
コールスタック
このプログラムの例のように、実行中に例外が発生した場合に、まず大切なことは、それがどこで発生したものかを調べることである。
関数呼び出し順序の階層関係は、コールスタックと呼ばれ、[表示]メニューの[デバッグウインドウ]->[コールスタック]で表示されるコールスタックウインドウで確認できる。
コールスタックウインドウでは、関数の呼び出し順に下から表示され、呼び出された時の引数、次の関数を呼び出した位置が確認できる。また、関数名の表示された行をダブルクリックすると、ソースコードの対応する位置へジャンプする。
コールスタックウインドウを表示し、例外が発生した状態でのコールスタックの状態を確認せよ。関数名をダブルクリックし、ソースコードの該当位置を調べよ。
例外の発生した位置は、メイン関数の以下の図で示された位置であることがわかる。
scanf 関数は、値を受け取る変数のアドレスを受け取る。(課題1 出力と入力参照)サンプルプログラムでは、変数 n の値を scanf 関数に渡しているために、アクセス例外が発生している。
さらにコールスタックウインドウを確認すると、main 関数は、mainCRTStartup 関数から呼び出されていることがわかる。(課題2 main も関数.では誰が呼び出すの?参照) mainCRTStartup 関数は、Visual C++処理系のライブラリ初期化などを行っているスタートアップルーチンである。さらに、mainCRTStartup ルーチンは、KERNEL32 から呼び出されていることがわかる。これは、Windowsオペレーティングシステムそのものである。
プログラム起動の指令を受けたオペレーティングシステムは、プログラムをメモリにロードし、エントリポイント(プログラムの開始点)である、スタートアップルーチンを呼び出している。
一旦デバッグを中断し、このプログラムのバグを修正した後にビルドする。プログラムの実行を行い、階乗が正しく計算されることを確認せよ。(デバッガ上で実行すると、プログラム終了時にウインドウが閉じてしまい結果を確認できないので、[ビルド]メニューの[実行](あるいは、CTRL+F5)で実行せよ。)
再帰呼び出し
再帰呼び出しとは、関数がその関数自身を呼び出すことである。再帰呼び出しを用いることで、複雑な処理を非常に単純なコードで実装できる場合があり、階乗計算はその最たる例である。
(2004年度 データ構造とアルゴリズム 第4回資料より)
コールスタックウインドウで、再帰呼び出しの様子を確認してみよう。
ソースプログラムの result = factorial(i); // ←ここにブレークポイントを設定 の行にブレークポイントを設定し、デバッガ上で実行する。階乗を求める値には「9」を入力することとする。
ブレークポイントで停止後にトレース実行を行い、コールスタックの様子を確認する。トレースは「ステップイン」を用いて、呼び出される関数の内部までトレースするようにすること。
トレース実行を行うと、factorial 関数が9、8、7... と引数をデクリメントしながら呼び出されている様子が確認できる。
スタックフレーム
関数の呼び出し時には、引数の受け渡し、戻り番地の保存、ローカル変数の格納にスタック領域が使用される。この領域はスタックフレームと呼ばれる。(課題2 C 言語のメモリ領域 (4) スタックフレーム参照) スタック領域の先頭アドレスの保存には、CPU内のスタックポインタと呼ばれるレジスタが使われる。教育用計算機システムのパーソナルコンピュータで使用されている Intel の 32ビットCPUのスタックポインタは ESP レジスタである。また、現在実行中の命令のアドレスは、インストラクションポインタレジスタ(EIPレジスタ)に格納されている。
スタックフレームのような広い範囲のメモリ空間の状態を調べるには、デバッガのメモリウインドウを使用するのがよい。メモリウインドウでは、任意の位置のメモリマップを表示できる。
ここでは実際のスタックフレームの様子を、以下の手順で確認してみよう。
1) result = factorial(i); の行にブレークポイントが設定されていることを確認し、デバッガ上で実行を行う。階乗を計算する値として、9を入力する。
2) ウォッチウインドウのシンボル名フィールドに、esp、eip と入力する。ここで、上記レジスタの値を確認することができる。ウォッチウインドウの上で右クリックし、コンテキストメニューから[16進表示]を選択し、値の表示を16進数とする。
(レジスタの値は、[レジスタウインドウ]でも確認することができる。
3) [表示]メニューから[デバッグウインドウ]->[メモリ]をクリックしメモリウインドウを開く。
4) 表示を見やすくするために、4バイトごとに表示されるようにメモリウインドウサイズを調節する。
5) メモリウインドウの[アドレス]ボックスに esp と入力し、エンターキーを押す。espに格納されたアドレスが、最上位の行に表示されるので、スクロールバーのスクロールボタン(上向き三角のボタン)を押して、espのアドレス(図では0x0012ff6c)番地が、最下位の行に来るようにする。
6) ステップイン実行を行い、スタックポインタの値とともにメモリウインドウの様子を確認する。
トレース実行を行っていくと、以下のようにスタックが使われていく様子が確認できる。
Intel系のCPUは、複数のバイト列からなるデータを、下位バイトから順にメモリに格納するリトルエンディアン方式をとっているので、メモリウインドウで表示される順番は逆に見えるので注意されたい。
関数の呼び出し側は、まず引数をプッシュした後に、CALL命令で関数を呼び出す。(CALL命令は、戻り番地をプッシュした後に、呼び出し番地へジャンプする。)
Intel系のCPUを用いる処理系では、ローカル変数へのアクセスのためにベースポインタ(EBP)というレジスタを使用してい る。呼び出された関数 の側では、EBPの値もスタックに保存している。この例では使用していないが、ローカル変数を使用する関数では、そのための領域もスタックにとられる。
C言語がどのように機械語に翻訳されて動作しているかは、混合モードウインドウ([表示]メニューの[デバッグウインドウ]->[混合モード])で表示されるので、より興味のある者は参考にするとよい。
練習課題:factorial 関数内にローカル変数を追加して実行した場合、スタックフレームの状態がどのように変化するかを調べよ。