mipsで書く再帰
学校を休んだ時特有の隙間時間すき
再帰とは
簡単に言うなら関数の中に関数がある状態。
例えば再帰で１～Nまでの和を出すプログラムをcで書くと
int sigma(int n){
int s;
if(n==0) return 0;
s=sigma(n-1);
return n+=s;
}
}
となる。再帰部分を除けばsigma(n)の中身はn += sだけ。
イメージとしてはとりあえずsigma(N)~sigma(1)までの
関数を作って待機させて、sigma(0)になったらブレイクして
待機させていた関数が逆から実行されていくといった感じですね。
レッツミップス
これをmipsで書こうと思った人間は三秒で気づくでしょうが
普通のジャンプ命令だと気が狂いそうになります。
一秒で考えつくのは0の時にj (待機させたとこ),それ以外の時にj(関数の最初)ですが
これだと0と１で無限ループします。そもそも再帰ですから
ifやforのような書き方は不可能なんですね。
そこでjではなくjalを使いましょう。動作自体はジャンプ命令と同じですが
ジャンプ命令動作時のPC+4の値がレジスタraに保存してくれます。
そしてもう一つ、jrというものがあります。これも動作はジャンプですが
飛ばす先をタグではなくレジスタの中身を見て判断します。
つまり、jalで飛ぶ前の次の命令の位置をraに記憶させ
飛ばした先でjr $raとすれば、戻ってこれるわけです。
ちなみにパイプラインプロセッサでは保存の際もPCは動きますので
実際にはジャンプ命令の２つ先のPCが保存されるので気をつけましょう。
スタックポインタ
しかし、c言語と違って一回に記憶させられる戻り先は一つまでです。
何回も再帰させれば、当然途中の戻り先情報、変数の値は消えます。
高級言語を使っていたときの甘えは捨てましょう。
話を戻すとそういう時はスタックポインタに値を保存しましょう。
初期値はものによりますが、そのCPUがとりうる最大の値です。
使い方としては
addi $sp, $sp, -(保存したい値×4)
sw $t0, 0($sp)
sw $t0, 4($sp)
...
とこんな感じです。最大の値が初期値ですから使う時は引いていきます。
読み込む時はlwしてあげた後に$spに引いた値を足していきましょう。
ちなみに実機ではspの初期値は不定値になっている場合があるので
その時はコードの最初でちゃんとした初期値を入れてあげましょう。
作ってみる
再帰の作り方が理解できたところで実際に作ってみると
addi $s0, $zero, 10 #Nの値
addi $t0, $t0, 0 #sの初期値
nop
j next
addi $sp, $sp, -8 :sigma
sw $ra, 0($sp)
beq $s0, $zero, end
sw $s0, 4($sp)
addi $s0, $s0, -1
lw $ra, 0($sp)
lw $s0, 4($sp)
add $t0, $t0, s0
addi $sp, $sp, 8 :end
jr $ra
:next
となります。jalを使う時は戻る前提なので
プログラムの最初でjalを使ってnopを挟んでjで
プログラム終了後の命令に飛ばす事で次に進みます。
そして、今回はパイプラインプロセッサという事で
分岐ハザードが起きることを前提にして分岐の直前に行う命令を
分岐の直後に記述しています。順序プロセッサだとバグるので注意。
それから、何もしない時に保存した値は使いません。
ですからロードを行わせずにspを進めて次に行かせます。
こんな感じで再帰はできます。挫折した人は再起してください。
ご精読ありがとうございました。
