サブルーチン(関数、手続き)2
現在、CSの勉強のために、コンピュータアーキテクチャ (電子情報通信レクチャーシリーズ)を読んでいる。
前回に引き続き、サブルーチン(関数、手続き)についてまとめていく。
サブルーチンが入れ子になっている場合
メインルーチンからサブルーチンAを呼び出し、そのままメインルーチンに戻る場合は、$ra
で戻りアドレスがわかるので問題はない。ただし、サブルーチンAの中で別のサブルーチンBを呼び出した場合、$ra
をサブルーチンAに戻るアドレスに上書きしてしまうと、サブルーチンAからメインルーチンに戻るアドレスがわからなくなってしまう。このような問題を解決するためにも、戻りアドレスをスタックに保存しておけばいい。
このように順番にスタックにプッシュしてデータを退避させておき、入れ子になっているサブルーチンの処理完了後にスタックからポップすることで退避していたデータを復元することができる。スタックのLIFOの性質を利用することにより、複雑な処理をすることなくサブルーチンの入れ子を実現することができている。
レジスタからメモリに退避するデータは以下が挙げられる。
- サブルーチンの引数
- サブルーチンの戻り先アドレス
- ローカル変数
- テンポラリ変数(ある処理をする都合上一時的に値を保存しておく変数)
これらの領域に必要なメモリサイズは、プログラムで宣言された型や式で決定されるので、コンパイル時に確定する。そのため、サブルーチン呼び出し時に、スタック領域の先頭から必要なサイズだけのメモリ領域を確保する。反対に、サブルーチンの処理が完了しリターンする時に、確保した領域を解放する。スタック領域の確保と解放は、スタック・ポインタ(SP)の加算・減算だけで行うことができる。
例題)再帰型手続のコンパイル
階乗を計算する再帰的手続きを考える。
int fact (int n) { if (n < 1) { return 1; } else { return n * fact(n-1); } }
この手続きをコンパイルした結果のMIPSのアセンブリコードを考える。
再帰関数を実行するにあたり、引数 $a0 と戻りアドレス $ra のレジスタをスタックに退避させる。返り値は$v0とする。
fact: addi $sp, $sp, -8 # スタックに2つの領域を確保する sw $ra, 4($sp) # 戻りアドレスを退避させる sw $a0, 0($sp) # 引数を退避させる slti $t0, $a0, 1 # n < 1であれば$t0=1。n > 1であれば$t0=0。 beq $t0, $zero, L1 # $t0=0であれば、L1に分岐 addi $v0, $zero, 1 # n < 1の場合、返り値$v0=1とする addi $sp, $sp, 8 # スタックを解放する jr $ra # 呼出し元に戻る L1: addi $a0, $a0, -1 # n > 1の場合、引数を-1する jal fact # 再帰で、factを呼び出す lw $a0, 0($sp) # 引数を復元させる lw $ra, 4($sp) # 戻りアドレスを復元させる addi $sp, $sp, 8 # スタックを解放する mul $v0, $a0, $v0 # 返り値$v0=n*fact(n-1)とする jr $ra # 呼出し元に戻る
手続きフレーム、アクティベーション・レコード
スタックに保存されるのは、サブルーチンの引数や戻りアドレスだけでなく、サブルーチン内でのローカル変数(配列やデータ構造など)やテンポラリ変数がある。スタックに確保した領域は、サブルーチンごとに固有であり、手続きフレーム(procedure frame)またはアクティベーション・レコード(activation record)と呼ばれる。
上記のプログラムでも示したように、手続きフレームに割り付けたデータはスタック・ポインタ($sp)からの相対アドレスでアクセスする。ただし、ローカル変数の中には動的にメモリを確保する機能があるものもあり、コンパイル時には確保しておくべき領域がわからないこともある。そのような場合に、スタック・ポインタ($sp)ではなく、手続きフレームの先頭を示すフレーム・ポインタ(frame pointer:$fp)をベースアドレスとしてアクセスする必要がある。MIPSでは、フレーム・ポインタをレジスタ30 $fp
に格納できるように割り当てをしている。プログラムの実行中にスタック・ポインタは変化する可能性があるので、プログラマーにとっては安定しているフレーム・ポインタを通じて変数を参照する方が容易であると言える。
グローバル・ポインタ
サブルーチンの中ではなく、メインルーチンに定義され、全てのサブルーチンからもアクセス可能な変数はグローバル変数と呼ばれる。グルーバル変数などの静的変数は、メモリの静的領域に格納される。MIPSでは静的なデータへのアクセスを単純化するために、静的領域のベースアドレスとして、グローバル・ポインタ(global pointer)をレジスタ28 $gp
に割り当てている。それぞれのグルーバル変数には、グローバル・ポインタからの相対位置でアクセスする。
まとめ
サブルーチンを理解することで、MIPSのレジスタ規約に関して、それぞれどのように使うべきか一通り確認することができた。