コンピュータアーキテクチャI課題解答例(第8回)

2014.11.26
コンピュータアーキテクチャI 課題解答例 (第 8 回)
1. 講義ノート 5 の演習 1 から演習 5 を行え．
演習 1：
答えはノートにある通り．自力でコンパイルして，ノートのような答えが出てきたか．出てこな
かったら何が間違っていたのかじっくり考えることが重要．
演習 2：
同上
演習 3：
省略
演習 4：
ハノイ関数：この関数は，棒 a にある n 枚の円盤を，棒 b をワークスペースとして使って，棒 c
に移す関数である．
関数本体でやっていることは，円盤 (n) が 1 枚だったら，それを棒 a から棒 c に移動して完了．
そうでなければ，1) 棒 a にある上から (n-1) 枚の円盤を棒 c をワークスペースとして使って棒 b に
移動し，2) 一番下にある円盤 (n) を棒 c に移動し，3) 棒 b にある (n-1) 枚の円盤を棒 a をワークス
ペースとして使って，棒 c に移動する，である．
関数 hanoi は再帰的に呼び出される．
関数 move は，円盤を移動するメッセージの出力を行う．
演習 5：
1) 省略
2)
hanoi:
#ここから 6 行でレジスタ退避
addi
sw
sw
$sp, $sp, -20
$a0, 0($sp)
$a1, 4($sp)
sw
sw
$a2, 8($sp)
$a3, 12($sp)
sw
slti
beq
$ra, 16($sp)
$t0, a0, 2
$t0, $zero, hanoi1
add
$a2, $a3, $zero
jal
lw
lw
move
$a2, 8($sp)
$ra, 16($sp)
# $a2 は値が変わったので，回復
# $ra は move を呼んだとき値が変わったので、回復
addi
jr
$sp, $sp, 20
$ra
#呼び出し元にジャンプ
hanoi1: addi
$a0, $a0, -1
#n-1
# n<2? n が 1 かどうかをチェック
# n>1 だったら分岐
# move(n,a,c) を呼ぶための準備．$a2
# に$a3 の値をコピー．
1
#ここから 3 行で$a2 と$a3 のスワップ
add
add
$t0, $a2, $zero
$a2, $a3, $zero
add
jal
$a3, $t0, $zero
hanoi
#hanoi(n-1,a,c,b);
lw
lw
jal
$a0, 0($sp)
$a2, 12($sp)
move
#n 回復
#c を$a2 に
#move(n,a,c)
addi
lw
$a0, $a0, -1
$a1, 8($sp)
#n-1
#$a1 に b
lw
lw
jal
$a2, 4($sp)
$a3, 12($sp)
hanoi
#$a2 に a
#$a3 に c
#hanoi(n-1,b,a,c)
lw
lw
$a0, 0($sp)
$a1, 4($sp)
#ここから 6 行でレジスタ回復
lw
lw
lw
$s2, 8($sp)
$s3, 12($sp)
$ra, 16($sp)
addi
jr
$sp, $sp, 20
$ra
#呼び出し元にジャンプ
参考 1 move 関数のコンパイル．
move:
addi
sw
$sp, $sp, -20
$a0, 0($sp)
sw
sw
sw
$a1, 4($sp)
$a2, 8($sp)
$a3, 12($sp)
sw
add
$ra, 16($sp)
$a3, $a2, $zero
#$a2 を$a3 にコピー
add
add
la
$a2, $a1, $zero
$a1, $a0, $zero
$a0, str1
#$a1 を$a2 にコピー
#$a0 を$a1 にコピー
#la ロードアドレス命令
#文字列 str1 の先頭アドレスを$a0 に
jal
printf
lw
lw
lw
$a0, 0($sp)
$a1, 4($sp)
$a2, 8($sp)
lw
lw
$a3, 12($sp)
$ra, 16($sp)
addi
jr
$sp, $sp, 20
$ra
静的データ領域
2
str1:
db
"move %d from %c to %c\n"
参考 2 printf 文などの可変引数関数のコンパイルについて
printf 文を例に話します．可変引数関数では，第 1 引数に第 2 引数以下をどのように使うかを指
示する情報を与えねばならない．たとえば，
printf("x= %d, y=%d\n", x, y);
なら，第 1 引数の内容から，第 2 引数と第 3 引数は整数であるとして処理することになる．具体的
には，printf 関数の本体において，第 1 引数の文字列を解読していって，%が来たら，その次の文
字を解析し，d なら第 2 引数を整数として読み出して，10 進数の文字列に変換して出力する．そし
て，第 1 引数の解析を継続する．というようにプログラムが組まれる．
（このあたりの詳細は，カー
ニハン，リッチィー：プログラミング言語 C 第 2 版の７．３節 (p.189) を見よ．
）
この関数の呼び出し部分のコンパイル例は以下のようになる．ただし，x,y はそれぞれ$s0,$s1 に
割り当てられているものとする．
add $a2, $s1, $zero
add $a1, $s0, $zero
#y を$a2 にコピー
#x を$a1 にコピー
la
#la は load address 命令
#str1 のアドレスを$a0 にロードする．
$a0, str1
jal printf
静的データ領域
str1:
db
x= %d, y=%d\n
#db は文字列を定義する擬似命令
#str1 のアドレスから"x= ..."の文字列が格
#納される．
このようになります．
引数の数が合わなかった場合どうなるか？
上の例で y を忘れた，すなわち，printf("x= %d, y=%d\n", x); と書いたとしましょう．そう
するとコンパイラは，次のようなコードを出します．
add $a1, $s0, $zero
#x を$a1 にコピー
la
#la は load address 命令
#str1 のアドレスを$a0 にロードする．
$a0, str1
jal printf
この場合，printf 本体では，第 1 引数の 2 番目の%d を見たとき，$a2 が y の値を持っていると解
釈して，その値を出力します．
（だから，y の正しい値は出力されないことになります．
）
3

Download Report