サブルーチン(関数、手続き)1
現在、CSの勉強のために、コンピュータアーキテクチャ (電子情報通信レクチャーシリーズ)を読んでいる。
今回は、サブルーチン(関数、手続き)の定義と呼出しの機能によって、プログラムに構造性とモジュール性を持たせる、サブルーチンを実現するための機構などについてまとめる。
サブルーチンとは
サブルーチンの構文は言語ごとに
と呼ばれており、ソフトウェアにおいて抽象化を実現する。メインルーチン(呼び出し側)から、サブルーチン(呼び出される側)が呼び出され、サブルーチンの中で処理が行われて、処理結果がメインルーチンに戻される。
サブルーチンを実現するためには、以下をどのように実現するかが問題となる。
- メインルーチンから、サブルーチンに引数をどのように渡すのか
- サブルーチンの実行結果をどのようにメインルーチンに渡すのか
- サブルーチンはどうやってメインルーチンに戻ってくるのか
前提として、コンピュータ内にデータのやり取りを行う場合、レジスタが最速である。よって、処理を高速化するためにも出来るだけレジスタだけを使用するようにしたい。サブルーチンのために割り当てられているレジスタは以下の通りである。
しかしながら、たいていのプログラムではレジスタの数よりも多くの変数が使用される。したがって、コンパイラは頻繁に使用される変数をレジスタに保持しておき、それ以外の変数をメモリ上に格納しようとする。そのために、ロード命令とストア命令を使用して、レジスタとメモリの間で変数のやり取りが発生する。このように使用頻度の低い変数、または後で必要となる変数を一旦メモリ上に格納(退避)することを、レジスタをスピル・アウト(spliling)すると言う。
レジスタをスピル・アウトするのに理想的なデータ構造が「スタック」である。スタックは、データの読み書きを「最新に書き入れたものから読み出す」方式(Last In First Out, LIFO)で行う点に特徴がある。スタックのどこに最新のデータが書き込まれているか、そのアドレスを格納しておくレジスタをスタック・ポインタ(Stack Pointer, SP)と呼ぶ。MIPSでは、スタック・ポインタ用にレジスタ29 $sp
が割り当てられている。
- プッシュ(PUSH):退避するデータをスタックに書き込み、データを積み上げていく
- ポップ(POP):退避していたデータをスタックから順番に読み出していく
そして、スタックは高いアドレスから低いアドレスに向かって伸びる。そのため、スタックにデータをプッシュする場合、スタックポインタから減算することを意味する。反対に、スタックからデータをポップする場合、スタックポインタに加算することになる。この点は、少し操作と演算で異なるので注意が必要である。
データをどのように保持しておくべきかがわかった時点で、最初の問いを考える。
メインルーチンから、サブルーチンに引数をどのように渡すのか
「引数を渡す」と言っているが、サブルーチンからアクセスできるレジスタに引数を保存(格納)しておき、サブルーチン側から読み出すことで実現する。ただし、レジスタの容量には限りがあるので、MIPSでは $a0 - $a3
を引数(argument)の保存用として割り当てている。引数用に4つのレジスタが確保されているので、最大4つの引数まではレジスタから読み出すことができる。ただし、第5引数以降はスタックに番号順にプッシュする。
サブルーチンの実行結果をどのようにメインルーチンに渡すのか
サブルーチンの戻り値(返り値)もレジスタに格納することで、メインルーチンで読み出すことができるようにする。MIPSでは、$v0 -$v1
を返り値用として割り当てている。($v0,$v1のvはvalueのvらしい。)
サブルーチンはどうやってメインルーチンに戻ってくるのか
メインルーチンの続きの処理に戻ってくるには、現在実行している処理のアドレスを保持しておけばいい。そこで、レジスタ31 $ra
を戻りアドレス(return address)を格納する場所として割り当てている。MIPSには、サブルーチン専用のジャンプ&リンク命令 jal
(jump-and-link)が用意されている。この命令を使うことで、サブルーチンの先頭アドレスに飛ぶと同時に、サブルーチン終了後に戻るべきアドレスを $ra
に格納してくれる。(一つの命令で二つの処理を実行してくれて便利である。)
上記より、サブルーチンを実行する流れは以下となる。
- メインルーチンでサブルーチンに渡す引数をレジスタに
$a0 - $a3
格納する。 - メインルーチンから、サブルーチンの先頭アドレスへジャンプする。それと同時に、メインルーチンへの戻りアドレスを
$ra
に格納する。- ジャンプ&リンク命令を使う。
jal X-address
- 現在のPC(プログラムカウンタ)が Y-Address の場合、サブルーチンから戻ってくるアドレスは
$ra = Y-address + 4
となる。
- ジャンプ&リンク命令を使う。
- サブルーチンの処理を実行する。
- 返り値を
$v0 -$v1
vに格納する。 - サブルーチンから、メインルーチンに戻す。
jr $ra
- メインルーチンの処理が再開される。
レジスタには限りがあることを上記でも述べたことであるが、メインルーチンからサブルーチンに処理が遷移した際に、レジスタのデータの保護の問題がまだ上記では検討されていない。例えば、メインルーチンで $s0
に大切なデータを格納していたとする。サブルーチンでも同様に $s0
を使うことになっていた場合、勝手にデータが上書きされてしまう可能性がある。この問題を解決する方法として、サブルーチンに遷移する前に、レジスタをスピル・アウトしておき、サブルーチンの処理が終わった後で、スタックからポップでデータを戻す方法が考えられる。
ただし、レジスタの全てのデータをスピル・アウトするとなると手間であり、無駄なデータまでスピル・アウトしてしまう可能性がある。そこで、MIPSでは、レジスタを2つのグループに分けている。
- $t0 - $t7, $t8 - $t9:一時変数用(temporary)は、サブルーチン側で保存しない。そのため、メインルーチンでは、この一時変数用にはサブルーチン側で上書きされてしまっては困るデータを格納しないようにする。絶対にデータを保護したい場合は、サブルーチンを呼び出す前に、スピル・アウトしておく必要がある。
- $s0 - $s7:退避変数用(spliling)は、サブルーチン側で使う場合に必ずメモリに退避および復元をする必要がある。
まとめ
サブルーチンを実行する流れは以下となる。
- レジスタをスピル・アウトする
$t0 - $t9
で保持しておきたいデータがあれば、メモリに格納しておく。(サブルーチン側で強制的に上書きされる可能性があるので注意)
- メインルーチンでサブルーチンに渡す引数をレジスタに
$a0 - $a3
格納する。 - メインルーチンから、サブルーチンの先頭アドレスへジャンプする。それと同時に、メインルーチンへの戻りアドレスを
$ra
に格納する。- ジャンプ&リンク命令を使う。
jal X-address
- 現在のPC(プログラムカウンタ)が Y-Address の場合、サブルーチンから戻ってくるアドレスは
$ra = Y-address + 4
となる。
- ジャンプ&リンク命令を使う。
- サブルーチンの処理を実行する。
$s0 - $s7
のレジスタを使う場合には、退避させる。
- 返り値を
$v0 -$v1
vに格納する。 $s0 - $s7
のレジスタで復元すべき箇所があれば、復元する。- サブルーチンから、メインルーチンに戻す。
jr $ra
- No.1でメモリに退避させているデータがあれば、レジスタに復元させる。
- メインルーチンの処理が再開される。