{% include head.html %}
ここから先はだんだんハードウェアに近い話が見えてくるので，ここでターゲット言語の MIPS アセンブリ言語について少し勉強しよう．本節では，MIPS アセンブリ言語でプログラムを実際に書いて，その動作を確認する．MIPS アーキテクチャについてはいわゆるパタヘネ本の和訳を読まれたい．（買って読んで損はない本である．）
本節の内容は MIPS に詳しい人から見ると不十分だったり不正確だったりする部分が多いかもしれない．改善のための提案には Issue を立ててもらうとありがたい．
ところで，自分が普段使っているマシンで MIPS のコードが直接動く人は多分いない．したがって，本節の内容を実行するには，MIPS のコードを動かすためのシミュレータが欲しい．そのようなシミュレータとして一番お手軽なのはSPIMである．これをインストールして使ってもよいのだが，ここではymyzk氏による拡張spim-for-kuisを勧める．インストール方法はspim-for-kuisのページを参照されたい．以下の例も spim-for-kuis での実行例である．
まずはシンプルなプログラムから見てみよう．以下のプログラムをex01.sとして保存してspim -file ex01.sを実行してみてほしい．spim-for-kuis が入っていれば，spim -show_stats -show_instructions -file ex01.s を実行すると，実行された命令と命令数に関する統計情報が出力される．（Armアセンブリ言語のためのハイライティングしか用意されていなかったので一部構文エラーの警告らしきハイライトが出ているが気にしないこと．）
{% include_relative mips/ex01.s %}
MIPS アセンブリのプログラムでは，各行に以下のいずれかが書かれている．
- 命令: 上の例では
addiu $sp,$sp,-20のような行は命令である．$spや-20等は命令の引数である．命令を実行すると，レジスタやメモリへ情報が読み書きされたり，次に実行する命令が決まったりする． - ラベル: 上の例では
main:のような行がラベルである．ラベルはアセンブリ中での場所を表している．次に実行すべき命令を指定するジャンプ命令はラベル名を用いてプログラムのどこにジャンプすべきかを決定することができる．アセンブラによってアセンブリプログラムが機械語に変換されるときには，データや各命令があらかじめ定められた仕様にしたがってバイナリに変換されるが，このときに各命令にもアドレスが付番される．各ラベルはこの変換後のアドレスに変換されてバイナリ中で使われる．（プログラム中の場所にも最終的にアドレスが振られるのだ，ということに注意しておいてほしい．） - ディレクティブ:
.textのようにドットで始まる行はディレクティブと呼ばれる．ディレクティブはアセンブリ中のどこにプログラムが書かれているか，どこにデータが書かれているか，このプログラム中でのグローバル関数名はどれかなどの情報をアセンブラに伝える役割がある．この講義の範囲では，深入りせずにおまじないと思っておいてもよい．
一行ずつ内容を説明しよう．
.text: 以降にプログラムが書かれていることを示すディレクティブである．.globl main:mainがグローバル関数mainの開始場所を表すラベルであることを示すディレクティブである．main:: ここから関数mainの定義が始まることを示すラベルである．addiu $sp,$sp,-20: 第1引数$spに第2引数$spと第3引数-20の和を書き込む命令である．$で始まる名前（例えば$sp）は レジスタ (register) と呼ばれる記憶領域を表しており，メモリに比べて数が限られているが読み書きが高速にできる．$spは スタックポインタ (stack pointer) と呼ばれる特別なポインタを保存するためのレジスタである．これについては関数呼び出しの節で詳しく説明するが，ここでは$spの値は (1) 関数定義の先頭で （関数本体によって決まる）一定量減らされ，(2) 関数から戻る前に同じ量だけ増やされる（したがって関数から戻った後の$spの値は関数が呼び出されたときの値と同じである）ことを覚えておいてほしい．li $v0,1: レジスタ$v0に整数定数1を書き込む命令である．アセンブリの文脈では定数のことを 即値 (immediate) と呼ぶことが多い．命令liは load immediate から来ているんだと思う．li $a0,20: 同様にレジスタ$a0に即値20を書き込む命令である．syscall: システムコール (system call) を発行する命令である．syscall命令は標準入出力の操作等を行うための命令で，命令実行時のレジスタ$a0とレジスタ$v0の値に応じて挙動が変わる．レジスタ$v0に1がセットされている状態でsyscallを呼び出すと，標準出力にレジスタ$a0の値（すなわちここでは20）が出力される．addiu $sp,$sp,20: 上で説明したように，関数から返る前に$spの値を戻す必要がある．この関数では先頭で$spの値を20減らしたので，関数から返る直前のここでのaddiu命令で20増やしている．jr $ra:jr命令はレジスタを引数に取る．レジスタには上述したプログラム中の場所を表すアドレスがセットされており，次に実行されるのはセットされているアドレスが振られている命令である．$raは リターンアドレス (return address) と呼ばれる特別なアドレスを保持するレジスタである．関数から返るべき先のアドレスがレジスタ$raに関数呼び出し時にセットされる決まりになっている．
注意: MIPS では分岐命令の直後に遅延スロットが生ずる（すなわち，分岐先の命令の前に分岐命令の直後に置かれた命令が実行されてしまう．）そのため，ここで挙げたコードは，遅延スロットに何もしない nop 命令を挿入する等して遅延スロットを潰さなければ実機では正しく実行されないはずである．しかし，SPIMシミュレータにおいてはこの遅延スロットが存在しないかのようにシミュレーションをしてくれるので，可読性のために，遅延スロットのことを考慮しないコードで説明を行っている．
例1のプログラムではレジスタを操作して計算を行う方法を示した．上述したようにレジスタは数が限られているので，より多くの記憶領域が必要になる場合にはメモリに保存すべき情報を読み書きすることになる．以下のプログラムは，メモリアクセスを行う計算を実装した例である．
{% include_relative mips/ex02.s %}
例1のプログラムと異なる部分について説明を加える．
li $t0,5: レジスタ$t0に即値5をセットする．sw $t0, 4($sp):swはメモリに 1 word の値を書き込む命令である．(sw= store word) この命令は，レジスタ（ここでは$t0）とメモリアドレス（ここでは4($sp)）を引数にとり，レジスタの値を指定したメモリアドレスに書き込む．4($sp)はメモリアドレスを指定するための式で，現在$spにセットされているメモリアドレスから4バイト先のアドレスを表す．したがって，この命令ではレジスタ$t0の値が$sp + 4で表されるアドレスに書き込まれる．$t0には前の命令で5がセットされているはずなので，ここではアドレス$sp + 4に値5が書き込まれる．lw $t1, 4($sp):lwはメモリから 1 word の値を読み出す命令である．(lw= load word) レジスタとメモリアドレスを引数にとり，このアドレスに保存されている値をレジスタに読みこむ．したがってこの命令ではアドレス$sp + 4に保存されている値がレジスタ$t1に読み込まれる．この時点ではアドレス$sp + 4には1つ前の命令で5が書き込まれているはずなので，この命令ではレジスタ$t1に5がセットされる．li $v0,1: レジスタ$v0に即値1をセットしている．2命令後のsyscallで使われる．move $a0,$t1: レジスタ$t1の値をレジスタ$a0にコピーする命令である．$t1の値は現在5なので，この命令ではレジスタ$a0に5がセットされる．syscall: ここでは$v0の値が1で$a0の値が5なので，標準出力に5が出力される．
このプログラムでは，メモリアクセスの仕方を示すために，値 5 をメモリを経由してレジスタ $t0 から $a0 にコピーするなど，意図的に無駄な命令を挟んでいる．メモリアクセスはレジスタへのアクセスに比べて遅いので，必要がなければこのようにプログラムを書くことは無いだろう．
MiniML4- には関数呼び出しが入っているので，関数呼び出しを MIPS アセンブリ言語でどのように書いたらよいかを理解することは重要である．ここでは関数がどのように実装されているかを学ぼう．
関数呼び出しをアセンブリ言語で実装するにあたっての問題点の一つは，関数の実行に必要な情報をメモリ上にどのように保存しておくかである．関数を呼び出し，計算を実行し，その後元の場所に戻るためには，少なくとも以下の情報を保持する領域をメモリ上に確保しておく必要がある．
- 関数にローカルな変数を保存するための記憶領域とそのアドレス: 関数は局所変数等のための記憶領域を使用して計算を行う．この局所変数のための領域が必要である．また，場合によっては関数に渡そうとしている引数を保持する領域も必要かもしれない．
- 関数呼び出しによって上書きされてしまうレジスタの内容を退避しておく領域: 以下で詳しく述べるが，上で
jr命令の説明で少し触れたように，関数を呼び出す際には戻ってくるべき命令のアドレスが特別なレジスタ$raにセットされる．したがって，関数の中で関数を呼び出す場合には，はじめの関数呼び出しの際にセットされた$raの内容をメモリに保存しておく必要がある．（さもなければ，2つ目の関数呼び出しの際に，1つ目の関数が終了した後に実行されるべき命令のアドレスを保持している$raが上書きされてしまう．）$raのような特別なレジスタの値のみならず，それ以外の汎用的なレジスタについても，呼び出し先の関数で上書きされては困るものについては，メモリに退避しておく必要があるだろう．
少しややこしいが，要は関数を正しく実行するためには，ローカルな記憶領域を呼び出しごとに確保する必要があるということである．
このローカルな記憶領域をメモリ上のどこに取るべきかは必ずしも自明ではない．例えばプログラム中で f という関数が定義されており，全部で 64 バイト のローカルな記憶領域が必要であったとしよう．「関数 f のための 64 バイトの記憶領域」を一箇所メモリ中に確保するだけでは十分ではない．なぜならば，f が再帰呼び出しを行っているかもしれないからである．f のための単一の記憶領域しか用意されていないとすると，再帰呼び出しのたびに領域が上書きされてしまい，呼び出しごとにローカルな記憶領域を確保するという目的を果たせない．かと言って，1回目の再帰呼び出し，2回目の再帰呼び出し．．．ごとに異なる記憶領域をあらかじめ確保しておくのでは，深い再帰が頻繁には行われない場合にほとんどの領域が無駄になってしまう．
この問題を解決するために通常用いられているのが，関数呼び出しのための記憶領域をスタックを用いて管理する方法である．この方法では，関数の先頭で必要なサイズのローカルな記憶領域をスタックの先頭に push し，関数から返る直前に記憶領域を pop する．これで関数呼び出しごとにローカルな記憶領域を確保することができ，かつ（関数呼び出しが終わったら記憶領域は解放されるので）メモリが無駄になることもない．
関数呼び出しは頻繁に行われることもあるので，スタックの操作やローカル領域へのアクセスが凄まじく複雑になるとプログラムの効率が悪化する．できるだけ簡単にスタック操作を行うために，実際には以下のような方法でローカル領域のスタックが実現されている．
- スタックの先頭のアドレスを常に保持するレジスタを定めておく．（MIPS では
$spである．） - 関数が呼び出されたときに，この呼び出し中に使う記憶領域を確保するために，
$spを必要な量だけ動かす．古い$spが保持するアドレスと，新しく$spが保持しているアドレスとの間の領域が，この呼び出しで使用して良い領域ということにする． - 関数から返る前に
$spの値を，確保したサイズ分だけ反対側に動かすことにより，ローカル領域を解放する．
歴史的な事情により，スタックはメモリアドレスの大きい方から小さい方に伸びることが多いようである．したがって，関数呼び出し時には $sp の値を減らし，関数から返るときには $sp の値を増やすことになる．
各関数呼び出しのローカルな記憶領域が保持されるこのスタックを コールスタック (call stack) と呼ぶ．また，関数呼び出しで確保されるローカルな記憶領域のことを スタックフレーム (stack frame) または アクティベーションレコード (activation record) と呼ぶ．スタックフレームに何を保存するかは，コンパイラに関数呼び出しを実装する上で考えなければならない重要事項の一つである．また，再帰呼び出しが深くなりすぎると スタックオーバーフロー (stack overflow) というメッセージが出ることがあるが，これは関数呼び出しの連鎖が深くなりすぎて，スタック上にスタックフレームを確保することができなくなったときに「スタックに使える領域が溢れて (overflowして) しまった」とユーザに伝えているのである．
関数呼び出しを実装するにあたってもう一つ大事なことは，関数を呼び出す際に引数をどのように関数に渡すか，関数から返るときに返り値をどのように呼び出し側に渡すかといった，関数を呼び出す際の呼び出し側と呼び出され側の挙動に関する約束事を決めておくことである．このような約束事のことを 呼び出し規約 (calling convention) と言う．
自分が実行する可能性のある関数をすべて実装する場合であれば，これは自分の好きなように決めればよい．しかしながら，このようなオレオレ呼び出し規約の問題点は，自分と異なる呼び出し規約を定めている人が書いたプログラムを呼び出すのが大変なことである．この場合，プログラム中で異なる呼び出し規約が混在することになって，プログラムを書くのも大変であり，可読性も悪くなる．コンパイラを書く側にしても面倒になる分大変である．
このようなオレオレ呼び出し規約に伴う問題を解決するために，アーキテクチャごとに標準の呼び出し規約が定められていることが多い．この規約に従ってプログラムを書けば（あるいはこの規約に従うコードを生成するコンパイラを書けば）標準呼び出し規約に従ったコード同士をリンクするのが容易になる．
呼び出し規約では，以下のような事項を定めておくことが多い．
- 引数の渡し方: 引数をどのレジスタに入れて渡すのか，スタックフレームのどこかに書いておいて渡すのか．
- 返り値の返し方: 返り値はどのレジスタに入れて渡すのか，スタックフレームのどこかに書いておいて渡すのか．
- レジスタの値を退避しておく義務の有無: 関数を呼び出す側と呼び出される側との間にレジスタに関する取り決めが何もないと，呼び出し側にとって重要なレジスタの値が関数によって上書きされてしまうといったような問題が起こる．そこで，呼び出し規約では caller-save registers と callee-save registers と呼ばれるレジスタの集合を定めて，各関数が柔軟にレジスタを使用できるようにすることが多い．
- レジスタ
rが caller-save registers に属する場合，呼び出し側は，rの値が関数実行後にも必要であるならば，この値をあらかじめ呼び出し前にスタックフレームに退避しておく必要がある．レジスタrは関数によって上書きされる可能性がある． - レジスタ
rが callee-save registers に属する場合，関数は返る前にrの値が関数先頭でのrの値と同じであることを保証する義務が生じる．したがって，もし関数がrを上書きする必要があるのであれば，関数は上書き前にrの値をスタックフレームに退避しておいて，関数が返る前にrの値を復元しなくてはならない．
- レジスタ
それでは，実際に関数呼び出しを行っているプログラム例を見てみよう．呼び出し規約は，以下の通り定められていることにする．（これは MIPS の標準的な規約とは必ずしも一致しない．）
- 引数は
$a0,$a1にセットして渡す． - 返り値は
$v0にセットして返す． - すべてのレジスタは caller-save である．
{% include_relative mips/ex03.s %}
少し説明を加える．ラベル main に続く部分は以下の通りである．
addiu $sp,$sp,-20: 上記の説明が分かれば，この命令はスタック上に今から使用するスタックフレームを確保していることがわかるであろう．この関数では 20 バイトを使用するので，$spの値を20減らしている．li $a0,5: 引数として渡す5を呼び出し規約通りに$a0にセットしている．sw $ra,0($sp): このあと関数fを呼び出すので，現在の関数が終わってから返るべき命令のアドレスを保持している$raの値をスタックフレーム上に退避している．スタックフレーム中のどこにどの情報を保存するかはいろいろなデザインがありうるが、今回は$raをアドレス$spに退避することにしよう．jal f:jal命令は関数が定義されているラベル名を引数に取り，そのラベルにジャンプする．このときに，関数から返るときの戻り先のアドレス（すなわちジャンプして来るべき命令のアドレスであるこの命令の次の命令）をレジスタ$raにセットする．ここで$raが上書きされるので，$raの値をこの前に退避しておく必要があるわけである．このように関数呼び出し時に戻ってくるべきアドレスを保持するレジスタを リンクレジスタ (link register) と呼ぶ．(jalは jump and link の略である．)lw $ra,0($sp): この命令は関数fから返ってきたときに実行される．退避しておいた$raの値を退避先のアドレス$spから復帰する．move $a0,$v0: 返り値$v0の値を$a0にコピーしている．コピーされた値が，このあとのsyscallで出力される値となる．li $v0,1:syscallに「標準出力への出力」を指示するために$v0に1をセットする．syscall: 標準出力に現在の$a0の値（すなわち，fからの返り値）を出力する．addiu $sp,$sp,20,jr $ra:$spの値を戻して$raの指す先に返る．
また，ラベル f に続く関数定義の部分は以下の通りである．
addiu $sp,$sp,-4: この呼び出しで使用する 4 バイト分のスタックフレームを確保する．（実際には使われていないが．）addiu $v0,$a0,2: 引数$a0に定数2を足した値を返り値を保持するレジスタ$v0にセットする．addiu $sp,$sp,4,jr $ra: 使用したスタックフレームを解放し，呼び出し元に戻る．
というわけで，f は受け取った値に 2 を加えて返す関数であるので，このプログラムを SPIM で実行すると 7 が標準出力に出力される．
最後に再帰関数を伴う例がどう実装されているかを見てみよう．ここまでの話が理解できていれば，そんなに難しくはない．ただし，再帰呼び出しに伴ってコールスタックがどのように伸びるか，再帰呼び出しから返る際にコールスタックがどのように縮むかを把握するのは重要である．
{% include_relative mips/ex04.s %}
ラベル main からラベル f の直前までの部分は，関数 f を引数 10 で呼び出し，その返り値を標準出力に出力している．（理解できているかどうかを自分で一応確認しておいてほしい．）関数 f がどのように実装されているかを見てみよう．
addiu $sp,$sp,-12: この呼び出しで使う 12 バイトのスタックフレームを確保している．ble $a0,0,end:bleは条件分岐を行うための命令である．第1引数（$a0）の値が第2引数（0）の値以下であるならばラベルendにジャンプし，そうでなければ次の命令を実行する．条件分岐命令は他にもあるが，とりあえず今回はこの命令だけ分かっていればよい．sw $a0,8($sp): 関数呼び出しを行うので，caller-save であり，関数呼び出し後にも使用するレジスタ$a0の値をスタックフレームに退避している．スタックフレーム内のどこに退避するかはこの呼び出しの中で矛盾なく決まっていればよい．今回は$a0を現在の$spから 8 バイト先の領域に退避することにしよう．addiu $a0,$a0,-1: このあと再帰的に呼び出すfに渡す引数を$a0にセットする．現在の$a0の値から 1 を引いた値を渡す．sw $ra,4($sp),jal,lw $ra,4($sp):$raの値を退避して，fを再帰的に呼び出す．返ってきたら，退避しておいた$raの値を復帰する．lw $a0,8($sp): 呼び出し前に退避しておいた caller-save であるレジスタ$a0を復帰する．addu $v0,$v0,$a0: 現在$v0には再帰呼び出しにより計算された返り値がセットされている．この値を$a0分だけ増やして，自分が呼び出し元に返す値とする．addiu $sp,$sp,12,jr $ra: スタックフレームを解放して呼び出し元に返る．
次に，$a0 が 0 以下であったときのジャンプ先であるラベル end 以下を説明しよう．
li $v0,0: 返り値0セットする．addiu $sp,$sp,12,jr $ra: スタックフレームを解放し，呼び出し元に返る．
さて，関数 f は全体としてどのような計算をしているのだろうか．また，再帰呼び出しによってコールスタックの様子はどうなるだろうか．ここまでが理解できていれば，f の開始時の $a0 の値が 3 などである場合にどのような計算が起こるかを手元で書き下してみればわかるはずである．ぜひ一度やってみてほしい．