サブルーチン呼び出しは、手続き呼び出し(procedure call) とも呼ばれる。 C 言語では、サブルーチンのことを関数と呼んでいるので、 サブルーチン呼出しは関数呼び出しと呼ばれる。
サブルーチン呼び出しを実現するには、次のような問題について考えなけれ ばならない:
ルーチンA サブルーチンB
│ ┌───→
↓ │ │
───┘ │
←──┐ │
│ │ │
│ │ ↓
│ └───←
↓
サブルーチンを呼び出す時は、サブルーチンに引数を渡さなければなら ない。高速化のため、引数はできるだけレジスタに入れて渡し、呼ばれたサ ブルーチンの側でそのレジスタから読み出すようにするのがよいが、レジス タの個数は限られている。そこで、MIPS では、第1〜第4引数を $a0 〜 $a3 に順に入れ、第5引数以降はスタックに番号順にプッシュするという規約に なっている。
例えば、ルーチン A が R16 に大事なデータを保持していたとする。 ルーチン A はサブルーチン B を呼び出すとする。もしも、B が R16 に勝 手な値を書き込んでしまったとすると、ルーチン A が R16 に保持していた 大事な値がルーチン B によって消されたことになり、困ってしまう。 この問題を解決する方法は、ルーチン B が R16 を使用する前に、R16 に入っ ていた値をどこかに退避し、ルーチン B の終了直前に、退避しておいた値 をR16 に戻してからルーチン A にリターンすることである。退避場所とし ては、スタックを使えばよい。(プッシュで退避、ポップで戻す)
しかし、ルーチン B が、自分の使うレジスタ全てについてこのような保存 処理をしなければならないとすると、手間がかかる。保存の必要のないレジス タもあるはずだ。
そこで、MIPS では R8 〜 R15, R24, R25 については、サブルーチン側で保 存しない、という規約を作った。これらレジスタには順に $t0〜$t7,$t8,$t9 という別名がついている(t は temporary の t)。呼び出し側では、これらの レジスタには、サブルーチン呼び出しで破壊されてもよい値を入れるようにす る。どうしても破壊されては困る場合は、呼び出し側のルーチンが保存・復帰 処理をする。
C プログラムの例で説明すると:
…
tmp = a;
a = b;
b = tmp; /* この3行で、a の値と b の値を交換。
交換が済んだら、tmp の値は要らない。*/
f(); /* だから、この f の呼び出しの際、tmp が入っていたレジスタ
は保存しなくてよい。だから、tmp は $t0 〜 $t10 のど
れかに入れておいて大丈夫。*/
…
というわけ。
R16 〜 R23 については、(一時的な値を入れるための変数として使ってもよ いが、)呼び出された側のルーチンで保存しなければならないと定められて いる。これらのレジスタには順に s0〜s7 という別名がつけられている。 (もちろん、サブルーチン側で使わないレジスタについては保存の必要はな い。)
サブルーチンが値を返す場合、レジスタ R2 に返すことになっている。た だし、2ワードの値を返したい場合もあるはずだから、その場合は R3 も使 う。R2, R3 には、$v0, $v1 という別名がつけられている。(v は value のv)
サブルーチンを使いたい時、単にそのサブルーチンの先頭番地にジャンプしたのでは、 サブルーチンの終了後どうやって元のルーチンに戻ればいいのかわからない。 そこで、戻るべき場所のアドレスをどこかに保存しながらジャンプする、 という工夫が要る。 そのために、jal (jump and link) 命令を用いる。 jal は、指定されたアドレスに飛ぶと同時に、 あとで戻るべき場所のアドレスを$31にしまってくれる。
jal 命令は次のような形をしている:
┌────┬────────────────────┐
│ 2 │ Target │
└────┴────────────────────┘
6 26
jal 命令を実行すると、サブルーチン実行後に戻るべき場所のアドレスをレ ジスタ R31 に入れてから Target が示すアドレスに分岐する。もちろん、 アドレスを直接書くのはかなわないので、アセンブリ言語ではアドレスの代わ りにラベルを書く。R31 には $ra (return address の頭文字)という別名 がついている。
※ところで、レジスタの名前は R0〜R31 ですが、アセンブリ言語では $0〜 $31 と書くので、私の文章でも $0〜$31 と書いていることがあります。R31 と書いたり $31 と書いたり不統一ですみません。
サブルーチンから戻る時には、
jr $ra
を実行する。 jr は、Jump register 命令というもので、
jr Rs
を実行すると、レジスタ Rs に入っている数値をアドレスとして、そのアドレ スにジャンプする。上で述べたように、サブルーチン呼び出しの際に jal は $ra に戻り先の番地を入れるので、jr $ra を実行すると、戻り先に戻れる ことがわかる。
ところで、ルーチン A が jal でサブルーチン B を呼び出した後、サブルー チン B がサブルーチン C を jal で呼び出したらどうなるか?
A:
│
│
↓
jal B ──────→ B: ($ra = (jal B の次の番地 X))
X番地: │
│
↓
jal C ─────→ C: ($ra = (jal C の次の番地 Y))
Y番地: ←─┐ │
│ │ │
│ │ ↓
│ └─── jr $ra
│
↓
jr $ra (!?)
($ra には Y が入っているから
X 番地に戻らずY 番地に飛んでしまうぞ!?)
1回目 の jal で $ra にしまわれた戻り番地(上図のX)が、2回目の jal で上 書きされてしまい、B の終了時に jr $ra を実行しても、元の A に戻れなく なるのではないか?
このような問題を避けるのは簡単である。jal C を実行するよりも前に、$ra を どこかに保存しておけばよい。そして、B が jr $ra を実行する前に $ra を復元する。保存先としてはもちろんスタックを使えばよい。
つまり、次のようにやり方を変えれば OK.
A:
│
│
↓
jal B ──────→ B: ($ra = (jal B の次の番地 X))
X番地: ←─┐ │
│ │ $ra の値(X)をスタックにプッシュ
│ │ │
│ │ ↓
↓ │ jal C ─────→ C: ($ra = (jal C の次の番地 Y))
│ Y番地: ←─┐ │
│ │ │ │
│ │ │ ↓
│ │ └─── jr $ra
│ │
│ $ra の元の値をスタックからポップ (X)
│ ↓
└───← jr $ra
このように、手続き呼出しの際にはスタックを多用する(スタックが伸び る)。スタック領域中で、手続き呼出しの際に伸びた部分を、その手続き呼出 しの「スタックフレーム」と言う。短く「フレーム」ということもある。
スタックフレームには、すでに述べたように、
が保持される。
スタックフレーム中のデータにアクセスするには、もちろんスタックポイン タを利用できる。lw $t0, 8($sp) とか sw $t1, 20($sp) などとすればよい。 しかし、スタックポインタの値は、スタックを利用するたびに変化するので、 スタックポインタの値を基点にしてメモリアクセスするのは、 ずいぶんややこしくなる。
そこで、コンピュータによっては、 スタックフレーム内のデータへのアクセスを簡単にするために、 フレームポインタと呼ばれるレジスタを置いていることがある。 (SGI 社のコンパイラはフレームポインタを使わないコードを吐くが、 GNU C コンパイラはフレームポインタを使う。) MIPS では、レジスタ R30 をフレームポインタに使用します。
R30 には $fp (frame pointer の頭文字)という別名がついている。 手続きの実行中、$fp にはスタックフレームの一番底のアドレスがずっと入っ ている。
低位のアドレス
↑
$sp →
┌────────┐
│ │
│ │
│ │
│ ローカル変数 │
│ │
│ │
│ │
├────────┤
│ │
│ │
│ │
│退避したレジスタ│
│(戻り番地を含む)│
│ │
│ │
├────────┤
│ 最後の引数 │
├────────┤
│ … │
├────────┤
│ 第6引数 │
├────────┤
$fp →│ 第5引数 │
└────────┘
↓
高位のアドレス
フレームポインタの値は、新しいフレームが作られるたびに新しく設定される ので、逆に言うと、手続きから戻る時には、以前の値に戻さなければならない。 そのため、手続き呼び出しの際には、フレームポインタの以前の値をスタッ クに保存する。
MIPS ベースのコンピュータ独得の規約として、スタックフレームのサイズ は最小でも32バイト取らなければならない、というものがある。仮引数や、退 避するレジスタの数が少なくても、必ず最低32バイトは取らないといけない。 (理由? 実は私も知りません。) このことは別に来学期以降忘れても構わない。 (他のタイプのコンピュータには関係ない話なので。)
スタックフレームの使い方も非常に重要なので、よく覚えておくこと。 これもわかっていないとソフトウェアを理解できない。
レジスタの別名がたくさん出てきたので、別名と用途についてまとめておく:
zero 0 常に0が入っている at 1 アセンブラが作業領域として使用するの(他の目的に使用不可) v0 2 式の評価結果や関数の返値を入れる v1 3 式の評価結果や関数の返値を入れる a0 4 第1引数を格納する a1 5 第2引数を格納する a2 6 第3引数を格納する a3 7 第4引数を格納する t0 8 一時変数(呼出し間で保存不要) t1 9 一時変数(呼出し間で保存不要) t2 10 一時変数(呼出し間で保存不要) t3 11 一時変数(呼出し間で保存不要) t4 12 一時変数(呼出し間で保存不要) t5 13 一時変数(呼出し間で保存不要) t6 14 一時変数(呼出し間で保存不要) t7 15 一時変数(呼出し間で保存不要) s0 16 一時変数(呼出し間で保存必要) s1 17 一時変数(呼出し間で保存必要) s2 18 一時変数(呼出し間で保存必要) s3 19 一時変数(呼出し間で保存必要) s4 20 一時変数(呼出し間で保存必要) s5 21 一時変数(呼出し間で保存必要) s6 22 一時変数(呼出し間で保存必要) s7 23 一時変数(呼出し間で保存必要) t8 24 一時変数(呼出し間で保存不要) t9 25 一時変数(呼出し間で保存不要) k0 26 OS が使用するので、他の目的に使用不可 k1 27 OS が使用するので、他の目的に使用不可 gp 28 静的データセグメントへのポインタ sp 29 スタック・ポインタ fp 30 フレーム・ポインタ ra 31 関数呼出しの際の戻りアドレスを格納
この表を暗記する必要はない。こういう使い分けの工夫をしているのだ、とい うことを理解すればよい。(ただし、$0 に 0 が入っているということは当面 覚えておこう。少なくとも試験が終るまでは…。)
下のような C プログラムを考える:
#include <stdio.h>
int main(int argc, char **argv, char **envp)
/* main は3つの仮引数を持つ。引数が実際に使われない時は
仮引数宣言を省略することも多いが…
3つ目の引数 envp はプログラミングA,B,C では教えていない */
{
printf("%d", square(10));
return 0;
}
int square(int n) /* f(n) は n * n を求めて返す。*/
{
return n * n;
}
これは、10の2乗を計算して印刷するプログラムである。 main ルーチンから関数 square を呼び出している。 square(n) は n * n を計算して返すだけの関数である。
これをコンパイルした結果のアセンブリコードは、printf を呼び出すので xspim でそのまま実行できない。そこで、printf を呼んでいる部分だけを xspim のシステムコールだけを使った形に修正したものを以下に示す。
関数の引数は $a0, $a1, …に入ること、関数の戻り値は $v0(つまり$2)に 入ることを思い出してから読むこと。
.text
.globl main
main:
subu $sp, $sp, 32 # スタックフレームは32バイト長
sw $ra, 20($sp) # 戻りアドレスを退避
sw $fp, 16($sp) # 古いフレームポインタを退避
addu $fp, $sp, 32 # 新しいフレーム・ポインタを設定
li $a0, 10 # 第一引数 10 を$a0 へ入れて
jal square # square を呼び出す。
move $a0, $v0 # square が返した値を$a0 へ
li $v0, 1 # システムコールprint_int の番号 1
syscall # システムコールで印刷
lw $ra, 20($sp) # 戻りアドレスを復元
lw $fp, 16($sp) # フレームポインタを復元
addu $sp, $sp, 32 # スタックフレームを巻き上げる(縮めて元に戻す)
jr $ra # main を呼んだ呼出し側へ戻る
square: # ここから square 関数
subu $sp, $sp, 32 # スタックフレームは最低32バイト長
sw $ra, 20($sp) # 戻りアドレスを退避
sw $fp, 16($sp) # フレームポインタを退避
addu $fp, $sp, 32 # フレームポインタを設定
mul $v0, $a0, $a0 # $a0 の内容 × $a0 の内容 を $v0 に入れる。
# $a0 には引数 n が入っていたので、
# n * n を $v0 に入れたことになる。
# 本来、かけ算の結果は HI と LO に入るのだが、
# mul を使うと、LO に入ったもの(積の下位32ビット)を、
# 通常のレジスタに入れてくれる。 (mul は疑似命令。)
# ここから、リターンの処理
lw $ra, 20($sp) # 戻りアドレスを復元
lw $fp, 16($sp) # フレームポインタを復元
addu $sp, $sp, 32 # スタック・フレームを巻き上げる
jr $ra # 呼び出し元へ戻る
このプログラムは http://www.kyoto-su.ac.jp/~kbys/kiso/cpu/square.s という名前で置いてあるのでxspimで実行してみるとよい。
「通常、オペレーティングシステムが入出力を行なう」と述べたが、どのよ うな命令を用いて入出力を行なうのだろうか? それには
の2つの方式がある。(I/O は Input/Output の略。)
特定のメモリアドレスに対してストア(書き込み)やロード(読み込み)を行 なうと、実際にはそのアドレスにはメモリはつながっておらず、入出力デバイ スがつながっていて、入出力デバイスとの間での信号・データの送受信が行な われる。
CPU から見ると、例えばハードディスク・コントローラとの間で信号やデー タのやりとりをするのも入出力になる。 コンピュータ全体を外から見た時には、ハードディスクは入出力装置とは 見なされず、普通、補助記憶装置に分類されるが、それはコンピュータの外 との間で入出力をしないからで、CPU から見れば、ハードディスクは CPU の外にあるから、CPU からハードディスクへのデータの送信は出力なので ある。
メモリ・マップドI/O 方式では、入出力のための特別な命令は必要ない。 MIPS ではこの方式を用いている。
I/O マップド I/O 方式では、入出力は専用命令によって行なわれる。 I/O 用のアドレスをメモリアドレスとは別に設ける。 例えば、全く架空の例だが、
といった具合である。 (レジスタはCPUだけにあるのではなく、デバイスコントローラなどにもある。) I/O 用のアドレス空間はメモリアドレス空間のように大きい必要はない。 Intel 8086 系 CPU (Pentium など)は I/O マップド I/O 方式を採用している。
通常の命令の実行の流れを一時中断して、何か別の処理を CPU にさせ、そ の後またもとの実行の流れに戻したい、ということがある。 そのために「例外(exception)」というしかけがある。 例外が発生すると、それまでの命令実行の流れは中断され、 実行は例外処理ルーチンと呼ばれるルーチンへうつる。 例外処理ルーチンが終了すると、実行 は(普通)元の流れへ戻る。
例外の発生の多くはいつ起こるか前もって予測できないものである。
例外の発生原因には次のようなものがある(これで全部というわけではない):
CPU の外部に発生原因があるような例外は、普通、 「割込み」と呼ばれる。
以下、これらについて説明しよう。
add Rd, Rs, Rt という命令を例にとる。この命令は、レジスタ Rs, Rt の内容を32ビット長の2の補数表現の整数とみて加算を行ない、その結果を Rd に格納する。この時、加算の結果が32ビット長の2の補数表現で表せる範 囲をはみ出してしまうことがある。このように算術演算の結果がレジスタに 入り切らなくなること(今考えている数値形式で表せる範囲を越えること)を 算術オーバフロー(あるいは短く「オーバフロー」)という。 add Rd, Rs, Rt 命令では、オーバフロー時には例外が発生し、例外処理ルー チンが呼び出される。
正の数どうしを加え合わせた場合、本来結果も正になるべきだが、桁あ がりの結果、最上位ビット(MSB)が 1 になってしまうことがあり得る。 MSB は符号ビットとして使われているから、結果が負の数として扱われてし まう。これをエラーと考えて特別なエラー処理をしようとするなら、add Rd, Rs, Rt 命令を使用し、例外処理ルーチンの中で適当なエラー処理を行 なうことになる。
C 言語では、算術オーバフローが起きても何らエラーとはしないことになっ ている。そこで、C コンパイラは、加算に対して add 命令ではなく、addu 命令を吐き出す。addu 命令は本来符号なし整数の加算命令で、MSB が符号 の意味を持たないので、オーバフローしても例外を発生させないことになっ ている。オーバフローを無視するなら、符号なし整数用の加算命令 addu を 符号あり整数の加算に使ってもよい。
算術オーバフローを起こし得る命令は決まっているので、どこで算術オー バフローが起こり得るかはわかるのだが、実際に起こるかどうかは演算をし てみないとわからない。その意味で、オーバフローによる例外は予測できな い。
算術オーバーフローによる例外は、CPU 内部に発生原因がある例外だと言える。 (従って、割込みとは呼ばれない。)
MIPS の機械語命令は32ビット長だが、32ビットで表せるすべての数値に 意味のある命令が対応しているわけではない。命令として意味を成さないビッ トパターンも存在する(未定義命令)。 もしもそのようなものを命令として実行しようとしてしまうと例外が発生する。 通常そのようなものを命令として実行することはないはずなのだが、 コンパイラが誤ってそのようなコードを吐くこともあり得るし、 コンパイラが吐いたプログラムの一部が何らかの原因で書き換わってしまった場合にもそういう事が起こり得る。 また、プロセッサの新しい版で追加された命令を使ったプログラムが古いプロセッサで誤っ て実行されることもあるだろう。 未定義命令が使用された場合、普通、それを実行したプログラムは停止さ せられる。
未定義命令の使用も、CPU の内部に発生原因がある例外であるといえる。
ハードウェアが異常な動作をした場合、プログラムの実行を継続できなく なることがある。そのような場合、例外を発生させ、例外処理ルーチンの中 で実行を停止する。
例えば、電源電圧が下がり始めた場合、完全に電源が切れる前に至急シャッ トダウン処理をすべきであろう。そのような場合を考えて、電源回路から異 常を知らせる信号が CPU に伝えられるようになっている事が多い。このケー スでは、例外の発生原因は CPU 外部にあるので、割込みと呼ばれる。
ハードウェアが異常な動作をした場合でも、それがノイズ等による一時的 なもので、回復処理がうまく行く場合は、実行を継続する場合がある。例外 処理ルーチンの中で回復処理(例えば入出力の再試行など)や、異常が起きた ことの記録などを行なったあと、元のプログラム実行の流れに戻る。
例えば、最近ではワークステーションだけでなく、パソコンでも ECC 付きの メモリを使用するものが増えてきた。ECC とは、誤り訂正符号 である。ノイズや放射線等でメモリ内容が書き換わったり、書き換わっていな くても読み取り誤りが生じることはあるが、ECC で検出・訂正できる範囲の狂 いなら訂正の上、プログラム実行を継続できる。しかし、それが頻繁に起こる ようなら原因を調べないといけないので、ECC のエラーは記録に残されること が多い。このケースも発生原因が CPU 外部にあるので割り込みである。
他に、異常な熱上昇でも割り込みが起こる。この場合、CPU が壊れるのを 避けるため、コンピュータ全体を停止させる。
また、CPU 自体が異常動作をした場合も例外が発生する。
キーボードやマウスからの入力はいつ起こるかわからない。だからといっ て、入力が起こったかどうか始終調べることをくり返すのは CPU パワーの 無駄である。そこで、入力が起こった時、それを CPU に知らせるのに例外 を発生させるのが普通である。例外処理ルーチンの中で、打鍵された文字の コードを記録したり、マウスの移動量を記録したりして、それがプログラム によって読み取れるようにする。これは CPU の外部に発生原因のある例外 なので、割込みと呼ばれる。
また、出力装置が出力を始めてから出力を終えるまでには長い時間がかか るので、CPU がそれをずっと待っているわけにはいかない。そこで、CPU は その間別の処理を続け、出力が完了したら、出力装置に割込みを発生させて もらう。
ユーザ・プログラムの中で、オペレーティングシステムのサービスを必要 とした時は、システムコールを行なう。これには、すでに触れた syscall 命令のような専用の命令を用いる。システムコール命令を発行すると、それ までのプログラム実行の流れが中断され、例外処理ルーチンはオペレーティ ングシステム内のルーチンに制御をうつす。 システムコールによる例外発生は、ユーザ・プログラム自体が発生させる ので、(1)〜(4)と違って予測できるものであるが、他の例外と同じ仕組みで 処理されるので、同じように例外と呼ばれる。
ところで、例外処理ルーチンから戻るにはどのようにすればよいのだろう か? サブルーチン呼出しの場合は、jal のような命令を使って、戻り番地を保 存してから分岐すれば良かった。しかし、例外発生は一般にいつ起こるかわ からないので、前もって戻り番地を保存しようとしても、保存する命令をい つ実行すればよいかわからない。従って、通常の命令実行によって(つまり、 ソフトウェア的に)戻り番地を保存するのは無理である。 そこで、例外が発生した場合は、ハードウェアが自動的に戻り番地を適当 な場所に保存するようになっている。MIPS の場合は、コプロセッサ 0 がこ の処理を行なっている。このような仕掛であるため、例外処理ルーチンから 元の流れに戻る時も、サブルーチンからの戻りと同じやり方ではできない。 そのため、例外処理から戻るための専用命令が用意されている。これ以上く わしい説明はなかなか大変なので、一年生向けとしてはこの辺でやめておく。
上で「例外」、「割込み」という言葉の使い分けを説明したが、実はこれは MIPS の世界での言い方である。困ったことに、コンピュータごとに、ある いは文献ごとに用語は異なっている。「例外(exception)」の代わりに 「トラップ(trap)」ということもある。 また、例外を全部ひっくるめて割込みと 呼ぶこともある。あるいは、ハードウェアが例外を起こす場合を単に割込み といい、システムコールのようにソフトウェアによって意図的に例外を起こ す場合を 「ソフトウェア割込み」 と呼ぶこともある。 ソフトウェア割込みの代わりに「割出し」 と呼ぶ文献もある。 MIPS の文献でも、例外処理ルーチンを 「割込みハンドラ」 と書いていたりする。 色々な文献を読む場合には注意すること。
ある種の処理の実行中には、割込まれたくないことがある。例えば、ある 割込みの処理中に同種の割込みが重ねて起こるとややこしい事になる場合が 多い。実行のタイミングにシビアな処理の途中にも割り込まれたくない。 その他、オペレーティングシステム回りでは割込み禁止の必要な局面がよ く生じる。 そこで、割込みマスクというものを用意して、 特定の種類の割込みを禁止できるようになっている。 割込みの種類を区別するためには、 割込みレベル (コンピュータによっては別の名前)というものが用意されていて、 割込みレベルごとに割込みを禁止したり許可したりできるようになっている。
システムコールはいつ起こるか予測できる。だから、例外ではなく、普通の サブルーチンコールでやればよいと思うかも知れないが、そうはいかない。 というのは、オペレーティングシステムのルーチンに入る時には特別な処理が 必要だからである。
サブルーチンコールの場合は、サブルーチンに飛んだあとでも、命令の実行 のされ方はコールの前と同じである。ところが、オペレーティングシステムの ルーチンに入る時は、 実行モードというものを変えなければならない。
CPU の実行モードには、(まともな CPU なら)少なくとも2つあり、それらは、 ユーザ・モード(または非特権モード)とカーネル・モード(または特権モード) と呼ばれる。(文献によって呼び方が違うこともある。) ユーザ・モードでは、実行が許可されていない命令が存在する。 それらは、「実行するには特権が必要な命令」という意味で、 「特権命令」と呼ばれている。 これに対して、カーネル・モードでは全ての命令の実行が許可されている。
ユーザが動かす普通のプログラムは、ユーザモードで動き、オペレーティン グシステム内のルーチンはカーネルモードで動く。
例えば、入出力命令はユーザ・モードでは実行できない。 入出力はオペレーティングシステムが一手に管理することになっているからである。 そのため、入出力をする時は、オペレーティングシステムのルーチンを呼び出す。 ただ、サブルーチンコールを使うと、 実行モードがカーネルモードに切り換わらないので、 別のしかけで呼び出さないといけない。そのために、例外を利用する。
ユーザ・モードの中にいる時は、モード切換えができない。 しかし、システムコールによって例外処理ルーチンに飛ぶときにカーネルモードに切換わる。 そして、システムコールから復帰するときに元のユーザ・モードに戻る。