トップ：http://galaxy.u-aizu.ac.jp/note/wiki/CAEX2015

swap手続き

第4版教科書上巻p.137の「2.13 Cプログラムの包括的な例題解説」にあるswap手続き(関数)を 本演習で利用可能な命令で実装したプログラムを示します。 教科書の該当分をよく読んで、C言語とMIPS命令との対応を理解すること。

C言語

void swap(int v[], int k)
{
  int temp;
  temp = v[k];
  v[k] = v[k+1];
  v[k+1] = temp;
}

アセンブリプログラム

swap:    addi $t1, $a1, 0 
         add $t1, $t1, $t1 
         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 $ra

引数の受け渡しは$a0と$a1のレジスタを使います。 ここでは、$a0でswapされる整列させる配列の先頭アドレスを、$a1でswapする箇所の配列の添え字(k)を受け渡します。

シフト命令は利用できないので、add命令の組み合わせで「k*4」を実現しています。

練習課題

以下のテンプレートと組み合わせて、swap関数の動作を確認すること。

       .data 
k:     .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 
       lw $a1, k 
       jal swap 
exit:  j exit 

ソート手続き

教科書に従い、swap関数を使って単純なソートプログラムの動作を確認します。

       .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 
       lw $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 

sort関数の、引数の受け渡しは$a0と$a1のレジスタを使います。 ここでは、$a0に整列させる配列の先頭アドレスを、$a1にNをそれぞれセットしています。

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

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

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

練習課題2

swap関数と組み合わせて、N = 3の時に正しく動作することを確認すること。 また、変数Nが10の場合に正しい結果が得られることを確認すること。

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

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

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

ファイル名は「ex04_p6.s」としてください。

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

第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

課題7：手続きを用いたプログラムの作成

下記の機能を実現する手続きを作成し、実行を確認してください。 作成するプログラムでは、main関数から、作成した関数(手続き)を呼び出し、動作を確認する部分も含めること。

16bit整数a, b, cを引数とし d = a*b + cを計算する関数: int mac(int a, int b, int c)

以下のパターンについて動作確認をすること。

(a, b, c) = (11, 21, 0)
(a, b, c) = (11, 21, 6)
(a, b, c) = (3333, 4444, 5555)

ファイル名は「ex03_p7a.s」としてください。

16bit整数aをn bit左シフトする関数: int left_shift(int a, int n)

動作確認は”0x1”を1, 4, 7, 15 bitシフトした結果を確認すること。シフト命令を使ってはいけない。

ファイル名は「ex03_p7b.s」としてください。