作成中

手続き呼び出し：ソート

mainプログラムから手続きを呼び出すプログラムの例を示します。 これは、第4版教科書上巻p.137の「2.13 Cプログラムの包括的な例題解説」にある整列アルゴリズムをもとに、 本演習で利用可能な命令で構成したソートをするプログラムです。 変数Nは要素数を表し、配列Aの先頭から整列される要素が格納されます。

引数の受け渡しは$a0と$a1のレジスタを使います。 ここでは、$a0に整列させる配列の先頭アドレスを、$a1にNをそれぞれセットしてから、ラベルsortから始まる整列アルゴリズムを手続きとして呼び出します。

        .data 
N:     .word 3 
A:     .word 32 
        .word 422 
        .word 83 
        .word 2 
        .word 92 
        .word 32 
        .word 97 
        .word 22 
        .word 4 
        .word 86 

        .text 
main:  la $a0, A           # $a0 = &A 
          lw $a1, N           # $a1 = N 
          jal sort 
exit:    j exit 

sort:  addi $sp, $sp, -20 
         sw $ra, 16($sp) 
         sw $s3, 12($sp) 
         sw $s2, 8($sp) 
         sw $s1, 4($sp) 
         sw $s0, 0($sp) 

         or $s2, $0, $a0     #move $s2, $a0 
         or $s3, $0, $a1     #move $s3, $a1 

         or $s0,$0,$0         # $s0(= i) = 0 

for1tst: slt $t0,$s0,$s3   # $t0 = (i < N) 1:0 
         beq $t0,$0,exit1    # if $t0 == 0 then exit1 
         addi $s1, $s0, -1   # j = i - 1 

for2tst: slti $t0, $s1, 0    # $t0 = (j < 0) 1:0 
         beq $t0, $0, cont   #bne $t0, $0, exit2 変更点2 
         j exit2 

cont:    or $t1, $s1, $0   # $t1 = j * 4 
         add $t1, $t1, $t1   #変更点3 
         add $t1, $t1, $t1 

         add $t2, $s2, $t1   # $t2 = &(A[j]) 
         lw $t3, 0($t2)         # $t3 = A[j] 
         lw $t4, 4($t2)         # $t4 = A[j+1] 

         slt $t0, $t4, $t3      # $t0 = (A[j]< A[j+1]) 1:0 
         beq $t0, $0, exit2  # if $t0 == 0 then exit2 
         or $a0, $s2, $0     # $a0 = $s2(&A) 
         or $a1, $s1, $0     # $a1 = $s1(j) 
         jal swap 

         addi $s1, $s1, -1 # j = j - 1 
         j for2tst 

exit2:   addi $s0, $s0, 1 # i = i + 1 
         j for1tst 

exit1:   lw $s0, 0($sp) 
         lw $s1, 4($sp) 
         lw $s2, 8($sp) 
         lw $s3, 12($sp) 
         lw $ra, 16($sp) 
         addi $sp, $sp, 20 
         jr $ra 

swap:    addi $t1, $a1, 0 
         add $t1, $t1, $t1    #変更点3 
         add $t1, $t1, $t1 
         add $t1, $a0, $t1 
         lw $t0, 0($t1) 
         lw $t2, 4($t1) 
         sw $t2, 0($t1) 
         sw $t0, 4($t1) 
         jr $31

教科書のプログラムとの変更点は以下のところです。

• move命令をor命令に置換
• bne命令をbeqとj命令の組み合わせに置換
• sll命令をadd命令に置換

$spは明示的に初期化されていませんが、xspimによって自動的に設定されます。

練習課題１

シミュレータで実行し、手続き(関数)呼び出しの実行経過を確認する。 JAL命令でPCが適切に変更されること、$31に戻り番地が格納されることも確認すること。

練習課題２

課題6：手続きを用いた行列の積アルゴリズム

第2回演習で作成した、行列の積を求めるプログラムのうち、二つの整数の積を求める部分を、手続きに置き換えなさい。

# 手続きのラベルは「MUL」にする。 # 引数は$a0と$a1を介して引き渡す。 # この手続きでは結果は$v0に保持する。 # メインプログラムでは、計算結果$v0を使って行列積をけいさんする。

実行経過を確認し、実行結果が依然と同じことを確認してください。

スタックを利用した手続き呼び出し

第4版教科書上巻p.105にある階乗を計算する再帰的手続きをもとに、スタックレジスタ($sp)の使いかたを理解します。 メインプログラムは、ラベルmainからはじまり、$a0にNをセットして手続きfactを呼び出します。 Nは要素数を指定し、結果はFNに格納します。

この手続きは自分自身を呼び出すので、$a0と$raレジスタをスタックに保持する必要があります。

        .data 
N:      .word 5 
FN:     .word 0 

.text 
main:   lw $a0, N         # $a0(= N) = 10 
        jal fact          # $v0 = fact($a0) 
        sw $v0 FN         # FN = $v0 
        exit: j exit 

fact:   addi $sp, $sp, -8 
        sw $ra, 4($sp) 
        sw $a0, 0($sp) 

        slti $t0, $a0,1   # $t1 = ($a0 < 1) 1:0 
        beq $t0, $0, L1   # if $t1 = 0 then L1 

        addi $v0,$0,1     # $v0 = 1 
        addi $sp,$sp,8    # $sp = $sp + 8 
        jr $ra            # return FN = 1 

L1:     addi $a0,$a0,-1 
        jal fact          # fact($a0 - 1) 
        lw $a0, 0($sp) 
        lw $ra, 4($sp) 
        addi $sp,$sp,8 
        mul $v0,$a0,$v0 
        jr $ra