トップ：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によって自動的に設定されます。
練習課題２
swap関数と組み合わせて、N = 3の時に正しく動作することを確認すること。 また、変数Nが10の場合に正しい結果が得られることを確認すること。
課題6：手続きを用いた行列の積アルゴリズム
第2回演習で作成した、行列の積を求めるプログラムのうち、2つの整数の積を求める部分を手続き呼び出しに置き換えなさい。
- 手続きのラベルは「MUL」にする。
- 引数は$a0と$a1を介して引き渡す。
- この手続きでは結果は$v0に保持する。
- メインプログラムでは、計算結果$v0を使って行列積を計算する。
ファイル名は「ex03_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
練習課題３
N = 5、8の時に、正しく階乗が計算できていることの動作を確認しなさい。特に、スタックポインタ($sp)について理解すること。
課題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」としてください。
