MIPSで様々なプログラムを書いてみる

概要

大学でアセンブリ言語を学んでいるので学んだ知識を共有できたらなということでJavaScriptとC言語で書かれたプログラムを色々MIPSアセンブラで書いていきます。今回は再帰関数をやっていきます。

1から任意の数nまでの合計 - その壱

数学のように書くとこのようになります。

\sum_{n=1}^{n}k

コードを見てもらった方が早いでしょう。
以下にJavaScriptとC言語のコードを載せておきます。

JavaScript

sum.js

function sum(n, res){
    if(n<1) return res;
    else return sum(n-1,res+n);
}

C言語

sum.c

int sum(int n, int res){
    if(n<1) return res;
    else return sum(n-1,res+n);
}

アセンブリ言語ではforやwhileの時と同じようにラベルを用いて、ループ処理のような感じで書いていきます。
そのままで解釈したMIPSコードを以下に示します。

SUM:
    addi $sp, $sp, -12
    sw   $ra, 0($sp)
    sw   $a0, 4($sp)
    sw   $a1, 8($sp)
    slti $t0, $a0, 1
    beq  $t0, $zero, SUM1
    add  $v0, $a0, $zero
    lw   $a1, 8($sp)
    lw   $a0, 4($sp)
    lw   $ra, 0($sp)
    addi $sp, $sp, 12
    jr   $ra
SUM1:
    add  $a1, $a1, $a0
    addi $a0, $a0, -1
    jal SUM
    lw   $a1, 8($sp)
    lw   $a0, 4($sp)
    lw   $ra, 0($sp)
    addi $sp, $sp, 12

少しだけ最適化出来るのでそのコードを以下に示します。

SUM:
    bne  $a0, $zero, SUM1
    add  $v0, $a0, $zero
    jr   $ra
SUM1:
    add  $a1, $a1, $a0
    addi $a0, $a0, -1
    jal SUM

今回のコードはint型なのでnの値が0になる瞬間が必ずあります。$a0つまりn=0の時、初めてn<1がFalseになるのでn!=0の時でSUM1にジャンプすればよいのでこうなります。今回の場合swとlwで値を保存しなくてもいいので

1から任意の数nまでの合計 - その弐

やってることは同じなのですが個人的に引数に計算途中のものを使うのが嫌なので少し変えます。展開されてから計算される感じなので処理速度的にはよろしくないです。

JavaScript

sum.js

function sum(n){
    if(n<1) return 0;
    else return n+sum(--n);
}

C言語

sum.c

int sum(int n){
    if(n<1) return 0;
    else return n+sum(--n);
}

以下アセンブリのコードです。

SUM:
    addi $sp, $sp, -8
    sw   $ra, 0($sp)
    sw   $a0, 4($sp)
    bne  $a0, $zero, SUM1
    addi $v0, $zero, 0
    lw   $a0, 4($sp)
    lw   $ra, 0($sp)
    addi $sp, $sp, 8
    jr   $ra
SUM1:
    addi $a0, $a0, -1
    jal SUM
    lw   $a0, 4($sp)
    add  $v0, $v0, $a0
    lw   $ra, 0($sp)
    addi $sp, $sp, 8
    jr   $ra

その壱のプログラムより少し複雑になっていますが、swで値を退避させる意味を私はこれで理解できました。

最後に

私も現在アセンブリ言語を学んでいる最中なので稚拙なコードですがご容赦ください。また、コードなどの間違いや誤字脱字等ありましたらコメントお願いします。それ以外の質問等もありましたらコメントください。自分の能力の限りで答えます。

参考

• MIPSプログラムの基本型
• MIPSで書く再帰
• MIPSリファレンスデータ(グリーンカード)