ソフトウェア基礎技術研修

制御の流れ
(分岐命令)
(教科書3.5節)
プロセッサの基本構成要素
PCの指す番地から取
得した命令を保持
次に実行する命
令の番地を記憶
プロセッサ
命令レジスタ
命令レジスタの内
容(取得した命令)
を解読
PC
デコーダ
ALU
算術演算や論
理演算を実行
プログラムの命令
とデータを格納.
レジスタ
・
・
・
主記憶
ALUで計算される
データを記憶
PC: Program Counter
九州大学工学部電気情報工学科
命令の実行手順
プロセッサ
命令レジスタ
アドレス
PC
0x00104
デコーダ
ALU
レジスタ
1.命令の取得:PCが指すアドレスの値をメモリ
から命令レジスタへ取得.同時に,次命令の
取得に備えてPCの値を更新(例えば+4)
主記憶
・・・
0x00104
add $t0, $s1, $s2
0x00108
sub $t1, $t0, $s3
0x0010c
lw $t1, 320($s4)
・・・
実際には,各命令は2進表現
でメモリに格納されている
2.命令の解読:命令レジスタの値をデコード
3.命令の実行:解読結果に従って実行
九州大学工学部電気情報工学科
命令の実行手順
PCの指す番地から取
得した命令を保持 プロセッサ
命令レジスタ
add $t0, $s1, $s2
実行する命令の
アドレス
アドレス
PC
0x00104
デコーダ
ALU
レジスタ
1.命令の取得:PCが指すアドレスの値をメモリ
から命令レジスタへ取得.同時に,次命令の
取得に備えてPCの値を更新(例えば+4)
主記憶
・・・
0x00104
add $t0, $s1, $s2
0x00108
sub $t1, $t0, $s3
0x0010c
lw $t1, 320($s4)
・・・
実際には,各命令は2進表現
でメモリに格納されている
2.命令の解読:命令レジスタの値をデコード
3.命令の実行:解読結果に従って実行
九州大学工学部電気情報工学科
命令の実行手順
プロセッサ
命令レジスタ
add $t0, $s1, $s2
次命令の取得にそ
なえてPCを更新
アドレス
PC
0x00108
デコーダ
ALU
レジスタ
1.命令の取得:PCが指すアドレスの値をメモリ
から命令レジスタへ取得.同時に,次命令の
取得に備えてPCの値を更新(例えば+4)
主記憶
・・・
0x00104
add $t0, $s1, $s2
0x00108
sub $t1, $t0, $s3
0x0010c
lw $t1, 320($s4)
・・・
実際には,各命令は2進表現
でメモリに格納されている
2.命令の解読:命令レジスタの値をデコード
3.命令の実行:解読結果に従って実行
九州大学工学部電気情報工学科
命令の実行手順
プロセッサ
命令レジスタ
add $t0, $s1, $s2
アドレス
PC
0x00108
デコーダ
ALU
取得した命令を解読
(s1とs2を加算し,t0へ格納)
レジスタ
1.命令の取得:PCが指すアドレスの値をメモリ
から命令レジスタへ取得.同時に,次命令の
取得に備えてPCの値を更新(例えば+4)
主記憶
・・・
0x00104
add $t0, $s1, $s2
0x00108
sub $t1, $t0, $s3
0x0010c
lw $t1, 320($s4)
・・・
実際には,各命令は2進表現
でメモリに格納されている
2.命令の解読:命令レジスタの値をデコード
3.命令の実行:解読結果に従って実行
九州大学工学部電気情報工学科
命令の実行手順
プロセッサ
命令レジスタ
add $t0, $s1, $s2
アドレス
PC
0x00108
デコーダ
加算
ALU
レジスタ
1.命令の取得:PCが指すアドレスの値をメモリ
から命令レジスタへ取得.同時に,次命令の
取得に備えてPCの値を更新(例えば+4)
主記憶
・・・
0x00104
add $t0, $s1, $s2
0x00108
sub $t1, $t0, $s3
0x0010c
lw $t1, 320($s4)
・・・
実際には,各命令は2進表現
でメモリに格納されている
2.命令の解読:命令レジスタの値をデコード
3.命令の実行:解読結果に従って実行
九州大学工学部電気情報工学科
命令の実行手順
PCの指す番地から取
得した命令を保持 プロセッサ
命令レジスタ
sub $t1, $t0, $s3
実行する命令の
アドレス
アドレス
PC
0x00108
デコーダ
ALU
レジスタ
1.命令の取得:PCが指すアドレスの値をメモリ
から命令レジスタへ取得.同時に,次命令の
取得に備えてPCの値を更新(例えば+4)
主記憶
・・・
0x00104
add $t0, $s1, $s2
0x00108
sub $t1, $t0, $s3
0x0010c
lw $t1, 320($s4)
・・・
実際には,各命令は2進表現
でメモリに格納されている
2.命令の解読:命令レジスタの値をデコード
3.命令の実行:解読結果に従って実行
九州大学工学部電気情報工学科
命令の実行手順
プロセッサ
命令レジスタ
sub $t1, $t0, $s3
次命令の取得にそ
なえてPCを更新
アドレス
PC
0x0010c
デコーダ
ALU
レジスタ
1.命令の取得:PCが指すアドレスの値をメモリ
から命令レジスタへ取得.同時に,次命令の
取得に備えてPCの値を更新(例えば+4)
主記憶
・・・
0x00104
add $t0, $s1, $s2
0x00108
sub $t1, $t0, $s3
0x0010c
lw $t1, 320($s4)
・・・
実際には,各命令は2進表現
でメモリに格納されている
2.命令の解読:命令レジスタの値をデコード
3.命令の実行:解読結果に従って実行
九州大学工学部電気情報工学科
命令の実行手順
プロセッサ
命令レジスタ
sub $t1, $t0, $s3
アドレス
PC
0x0010c
デコーダ
ALU
取得した命令を解読
(t0とs3を減算し,t1へ格納)
レジスタ
1.命令の取得:PCが指すアドレスの値をメモリ
から命令レジスタへ取得.同時に,次命令の
取得に備えてPCの値を更新(例えば+4)
主記憶
・・・
0x00104
add $t0, $s1, $s2
0x00108
sub $t1, $t0, $s3
0x0010c
lw $t1, 320($s4)
・・・
実際には,各命令は2進表現
でメモリに格納されている
2.命令の解読:命令レジスタの値をデコード
3.命令の実行:解読結果に従って実行
九州大学工学部電気情報工学科
命令の実行手順
プロセッサ
命令レジスタ
sub $t1, $t0, $s3
アドレス
PC
0x0010c
デコーダ
減算
ALU
レジスタ
1.命令の取得:PCが指すアドレスの値をメモリ
から命令レジスタへ取得.同時に,次命令の
取得に備えてPCの値を更新(例えば+4)
主記憶
・・・
0x00104
add $t0, $s1, $s2
0x00108
sub $t1, $t0, $s3
0x0010c
lw $t1, 320($s4)
・・・
実際には,各命令は2進表現
でメモリに格納されている
2.命令の解読:命令レジスタの値をデコード
3.命令の実行:解読結果に従って実行
九州大学工学部電気情報工学科
命令の実行手順
PCの指す番地から取
得した命令を保持 プロセッサ
命令レジスタ
lw $t1, 320($s4)
実行する命令の
アドレス
PC
0x0010c
・・・
デコーダ
ALU
主記憶
アドレス
レジスタ
1.命令の取得:PCが指すアドレスの値をメモリ
から命令レジスタへ取得.同時に,次命令の
取得に備えてPCの値を更新(例えば+4)
0x00104
add $t0, $s1, $s2
0x00108
sub $t1, $t0, $s3
0x0010c
lw $t1, 320($s4)
・・・
実際には,各命令は2進表現
でメモリに格納されている
2.命令の解読:命令レジスタの値をデコード
3.命令の実行:解読結果に従って実行
以降,繰り返し・・・
九州大学工学部電気情報工学科
逐次制御だけで十分なのか?
 命令実行に関する基本動作
 主記憶に格納された命令を1個ずつ,順番に実行する(逐次制御)
 全ての場合に対応できるのだろうか?
A[80] = (g + A[2]) – (h + A[i]);
lw $t0, 8 ($s4)
add $t0, $t0, $s1
add $t1, $s3, $s3
add $t1, $t1, $t1
add $t1, $t1, $s4
lw $t1, 0 ($t1)
add $t1, $t1, $s2
sub $t1, $t0, $t1
sw $t1, 320 ($s4)
逐次制御で問題なし!
if (i == j)
f = g + h;
else
f = g – h;
???
逐次制御だけでは対応できない!
条件に応じて分岐する必要がある!
九州大学工学部電気情報工学科
MIPSの命令(一部)
命令
命令区分
算術演算 add
データ転
送
意味
add $s1, $s2, $s3
$s1 = $s2 + $s3
Subtract
sub $s1, $s2, $s3
$s1 = $s2 – $s3
load word
lw $s1, 100($s2)
$s1に,メモリの[$s2+100]番地の
ワードデータを読込み
store word
sw $s1, 100($s2)
メモリの[$s2+100]番地に,$s1の
ワードデータを書込み
beq $s1, $s2, L
もし、$s1==$s2ならLへ分岐
branch on not
equal
bne $s1, $s2, L
もし、$s1!=$s2ならLへ分岐
set on less than
slt $s1, $s2, $s3
もし、$s2<$s3なら$s1=1, 以外なら
$s1=0
jump
jL
Lにジャンプ
jump register
jr $s1
$s1の値が示すアドレスにジャンプ
条件分岐 branch on equal
無条件
ジャンプ
例
$s1~$s3は汎用レジスタ
九州大学工学部電気情報工学科
ラベル名
ラベル名: 命令やデータが配置されている主記憶上の番地につけ
られた名前.
100
add
$s0, $s0, $s1
add
$s0, $s0, $s1
104
addi
$s4, $zero, 1
addi
$s4, $zero, 1
108
add
$s1, $s1, $s0
add
$s1, $s1, $s0
112
sub
$s0, $s0, $s4
sub
$s0, $s0, $s4
116
bne
$s0, $s4, 108番地
bne
$s0, $s4, L1
L1:
ラベル定義
ラベル参照
ラベル名はアセンブラによって実際の番地に変換される.
九州大学工学部電気情報工学科
条件分岐命令(1)
条件分岐命令がない場合
①
②
③
④
add $s1, $s2, $s3
add $t0, $s1, $s4
lw $t1, 8 ($s5)
sub $t1, $t1, $t0
命令実行の流れ
条件分岐命令がある場合
① add $s1, $s2, $s3
② beq $s1, $s6, GoTo
add $t0, $s2, $s4
sw $t0, 8 ($s5)
①
②
③
④
GoTo:
③ add $s4, $t4, $t3
④ sw $s4, 8 ($s5)
②で分岐条件が成立
した場合
分岐条件が不成立
の場合
九州大学工学部電気情報工学科
条件分岐命令(2)
例)
beq $s0, $s1, L1
レジスタ$s0の値と$s1の値を比
較して,同じであればラベルL1
へ分岐(PCの値を設定)
beq: Branch on EQual
bne $s0, $s1, L1
beq
$s0, $s1, L1
$s0 = $s1
Yes
No
次の命令
bne
ラベルL1の番地
$s0, $s1, L2
レジスタ$s0の値と$s1の値を比
較して,同じでなければラベル
L1へ分岐(PCの値を設定)
$s0  $s1
bne: Branch on Not Equal
次の命令
Yes
No
ラベルL2の番地
九州大学工学部電気情報工学科
条件分岐命令(3)
プロセッサ
命令レジスタ
アドレス
PC
0x00104
デコーダ
ALU
レジスタ
1.命令の取得:PCが指すアドレスの値をメモリ
から命令レジスタへ取得.同時に,次命令の
取得に備えてPCの値を更新(例えば+4)
2.命令の解読:命令レジスタの値をデコード
主記憶
・・・
0x00104
beq $t0, $s1, L1
0x00108
add $t1, $t0, $s3
0x0010c
lw $t1, 320($s4)
L1
・・・
0x00400
lw $t1, 120($s4)
・・・
実際には,各命令は2進表現
でメモリに格納されている
3.命令の実行:解読結果に従って実行
九州大学工学部電気情報工学科
条件分岐命令(3)
PCの指す番地から取
得した命令を保持 プロセッサ
命令レジスタ
beq $t0, $s1, L1
実行する命令の
アドレス
アドレス
PC
0x00104
デコーダ
ALU
レジスタ
1.命令の取得:PCが指すアドレスの値をメモリ
から命令レジスタへ取得.同時に,次命令の
取得に備えてPCの値を更新(例えば+4)
2.命令の解読:命令レジスタの値をデコード
主記憶
・・・
0x00104
beq $t0, $s1, L1
0x00108
add $t1, $t0, $s3
0x0010c
lw $t1, 320($s4)
L1
・・・
0x00400
lw $t1, 120($s4)
・・・
実際には,各命令は2進表現
でメモリに格納されている
3.命令の実行:解読結果に従って実行
九州大学工学部電気情報工学科
条件分岐命令(3)
プロセッサ
命令レジスタ
beq $t0, $s1, L1
次命令の取得にそ
なえてPCを更新
アドレス
PC
0x00108
デコーダ
ALU
レジスタ
1.命令の取得:PCが指すアドレスの値をメモリ
から命令レジスタへ取得.同時に,次命令の
取得に備えてPCの値を更新(例えば+4)
2.命令の解読:命令レジスタの値をデコード
主記憶
・・・
0x00104
beq $t0, $s1, L1
0x00108
add $t1, $t0, $s3
0x0010c
lw $t1, 320($s4)
L1
・・・
0x00400
lw $t1, 120($s4)
・・・
実際には,各命令は2進表現
でメモリに格納されている
3.命令の実行:解読結果に従って実行
九州大学工学部電気情報工学科
条件分岐命令(3)
プロセッサ
命令レジスタ
beq $t0, $s1, L1
アドレス
PC
0x00108
デコーダ
取得した命令を解読
ALU
(t0==s1ならL1へ分岐)
レジスタ
1.命令の取得:PCが指すアドレスの値をメモリ
から命令レジスタへ取得.同時に,次命令の
取得に備えてPCの値を更新(例えば+4)
2.命令の解読:命令レジスタの値をデコード
主記憶
・・・
0x00104
beq $t0, $s1, L1
0x00108
add $t1, $t0, $s3
0x0010c
lw $t1, 320($s4)
L1
・・・
0x00400
lw $t1, 120($s4)
・・・
実際には,各命令は2進表現
でメモリに格納されている
3.命令の実行:解読結果に従って実行
九州大学工学部電気情報工学科
条件分岐命令(3)
プロセッサ
命令レジスタ
beq $t0, $s1, L1
比較
デコーダ
(結果は一致!)
ALU
アドレス
PC
0x00108
レジスタ
1.命令の取得:PCが指すアドレスの値をメモリ
から命令レジスタへ取得.同時に,次命令の
取得に備えてPCの値を更新(例えば+4)
2.命令の解読:命令レジスタの値をデコード
主記憶
・・・
0x00104
beq $t0, $s1, L1
0x00108
add $t1, $t0, $s3
0x0010c
lw $t1, 320($s4)
L1
・・・
0x00400
lw $t1, 120($s4)
・・・
実際には,各命令は2進表現
でメモリに格納されている
3.命令の実行:解読結果に従って実行
九州大学工学部電気情報工学科
条件分岐命令(3)
プロセッサ
分岐先アドレスに更新!
命令レジスタ
アドレス
beq $t0, $s1, L1
PC
比較
デコーダ
(結果は一致!)
ALU
0x00400
レジスタ
1.命令の取得:PCが指すアドレスの値をメモリ
から命令レジスタへ取得.同時に,次命令の
取得に備えてPCの値を更新(例えば+4)
2.命令の解読:命令レジスタの値をデコード
主記憶
・・・
0x00104
beq $t0, $s1, L1
0x00108
add $t1, $t0, $s3
0x0010c
lw $t1, 320($s4)
L1
・・・
0x00400
lw $t1, 120($s4)
・・・
実際には,各命令は2進表現
でメモリに格納されている
3.命令の実行:解読結果に従って実行
九州大学工学部電気情報工学科
条件分岐命令(3)
PCの指す番地から取
得した命令を保持 プロセッサ
命令レジスタ
lw $t1, 120($s4)
実行する命令の
アドレス
アドレス
PC
0x00400
デコーダ
ALU
レジスタ
1.命令の取得:PCが指すアドレスの値をメモリ
から命令レジスタへ取得.同時に,次命令の
取得に備えてPCの値を更新(例えば+4)
2.命令の解読:命令レジスタの値をデコード
主記憶
・・・
0x00104
beq $t0, $s1, L1
0x00108
add $t1, $t0, $s3
0x0010c
lw $t1, 320($s4)
L1
・・・
0x00400
lw $t1, 120($s4)
・・・
実際には,各命令は2進表現
でメモリに格納されている
3.命令の実行:解読結果に従って実行
九州大学工学部電気情報工学科
条件分岐命令(4)
例)
slt $s0, $s1, $s2
レジスタ$s1の値と$s2の値を比較
して,$s1<$s2であれば$s0に値
「0」を,そうでなければ値「1」を格
納(分岐条件の設定に利用)
slt: Set on Less Than
Yes
$t0 ← 1
$s1 < $s2
No
$t0 ← 0
九州大学工学部電気情報工学科
無条件分岐命令(1)
分岐命令がない場合
①
②
③
④
add $s1, $s2, $s3
add $t0, $s1, $s4
lw $t1, 8 ($s5)
sub $t1, $t1, $t0
命令実行の流れ
無条件分岐命令がある場合
① add $s1, $s2, $s3
② j GoTo
add $t0, $s2, $s4
sw $t0, 8 ($s5)
GoTo:
③ add $s4, $t4, $t3
④ sw $s4, 8 ($s5)
常に分岐先を実行
九州大学工学部電気情報工学科
無条件分岐命令(2)
例)
j L1
常にラベルL1へ分岐(PCの値
を設定)
j: Jump
jr $s0
常に$s0に格納されている番地
へ分岐(PCの値を設定)
jr: Jump Register
九州大学工学部電気情報工学科
アセンブリ言語プログラムを書いてみよう!
問題:以下,4つの場合に関して,slt命令,beq命令,または,
bne命令を用いてアセンブリ言語プログラムを作成せよ.な
お,常にゼロの値を保持するレジスタ($zero)を用いて良い.
①「$s0 < $s1」 ならラベルLへ分岐
②「$s0 > $s1」 ならラベルLへ分岐
③「$s0 <= $s1」 ならラベルLへ分岐
④「$s0 >= $s1」 ならラベルLへ分岐
九州大学工学部電気情報工学科
コード例: C言語の goto 文
 ラベル名で指定するところに飛ぶ.
L100:
…
goto L100;
...
xxxx
L100:
j
…
xxxx
L100
九州大学工学部電気情報工学科
コード例: C言語の if 文(1)
 式の値が真(0以外の整数)ならば else の前を実行する.式の
値が偽(0)ならば else の後を実行する.文が複数ある場合は
中括弧でくくる.
if (式)
文;
else
文;
省略可能
if (式) {
文;
...
}
else {
文;
...
}
 式の値が偽のときに特にすることがなければ,else 以降は省
略してもよい.
九州大学工学部電気情報工学科
コード例: C言語の if 文(2)
L1:
L1:
if (i == j) goto L1;
f = g + h;
f = f – i;
beq
add
sub
$s3, $s4, L1
$s0, $s1, $s2
$s0, $s0, $s3
変数名
レジスタ
f
$s0
g
$s1
h
$s2
i
$s3
j
$s4
九州大学工学部電気情報工学科
コード例: C言語の if 文(3)
if (i == j)
f = g + h;
else
f = g – h;
ELSE:
EXIT:
bne
add
j
sub
…
$s3, $s4, ELSE
$s0, $s1, $s2
EXIT
$s0, $s1, $s2
変数名
レジスタ
f
$s0
g
$s1
h
$s2
i
$s3
j
$s4
九州大学工学部電気情報工学科
コード例: C言語の while 文(1)
1. 条件式を評価する.
2. 条件式の値が真(0以外の整数)ならば文または中括弧の中
を実行する.偽(0)ならば文または中括弧の中を実行せずに
次に進む(=ループを終了する).
3. 文または中括弧の中を実行した後は 1. に戻る.
while (条件式)
文;
while (条件式) {
文;
...
}
条件式が「真」の間,
繰り返し実行される
九州大学工学部電気情報工学科
コード例: C言語の while 文(2)
while (save[i] == k)
i = i + j;
save[i] の番地 = $s6 + $s3 * 4
WHILE:
EXIT:
add
add
add
lw
bne
add
j
…
$t0, $s3, $s3
$t0, $t0, $t0
$t0, $t0, $s6
$t1, 0($t0)
$t1, $s5, EXIT
$s3, $s3, $s4
WHILE
変数名
レジスタ
i
$s3
j
$s4
k
$s5
save[] 先頭番地
$s6
九州大学工学部電気情報工学科
コード例: C言語の switch 文(1)
 式の値と同じ値の case のところに飛ぶ.該当する case がな
い場合は default のところに飛ぶ.
switch (式) {
case 値1:
...
case 値2:
...
case 値3:
...
default:
...
}
式=値1のとき
式=値2のとき
式=値3のとき
式=その他の値のとき
省略可能
 default 以降は不要ならば省略してもよい.
九州大学工学部電気情報工学科
コード例: C言語の switch 文(2)
 通常,switch 文の各 case のあとには break 文を入れる.
 switch 文の中括弧の中で break 文を実行すると,中括弧の残
りの実行を打ち切り,switch 文の外に飛ぶ.
switch (式) {
case 値1:
...
break;
case 値2:
...
break;
default:
...
}
式=値1のとき
式=値2のとき
式=その他の値のとき
九州大学工学部電気情報工学科
コード例: C言語の switch 文(3)
switch (k) {
case 0:
f = i + j;
break;
case 1:
f = g + h;
break;
case 2:
f = g – h;
break;
case 3:
f = i – j;
break;
}
•kが「0」の場合
• f=i+j;だけが実行される
•kが「1」の場合
• f=g+h;だけが実行される
•kが「2」の場合
• f=g-h;だけが実行される
•kが「3」の場合
• f=i-j;だけが実行される
•kが「0,1,2,3以外の場合」
• switch本体は実行されない
九州大学工学部電気情報工学科
コード例: C言語の switch 文(4)
k == 0
Yes
f←i+j
No
k == 1
Yes
f←g+h
No
k == 2
Yes
f←g–h
No
k == 3
時間が
かかる!!
No
Yes
f←i–j
九州大学工学部電気情報工学科
コード例: C言語の switch 文(5)
表に登録されている
番地に分岐.
添え字
登録番地
0
L0
1
L1
2
L2
3
L3
k
k == 0
k == 1
k == 2
k == 3
L0: f ← i + j
L1: f ← g + h
L2: f ← g – h
L3: f ← i – j
九州大学工学部電気情報工学科
コード例: C言語の switch 文(6)
範囲検査
多岐分岐
L0:
L1:
L2:
L3:
EXIT:
slt
bne
slt
beq
add
add
add
lw
jr
add
j
add
j
sub
j
sub
…
$t3, $s5, $zero
$t3, $zero, EXIT
$t3, $s5, $t2
$t3, $zero, EXIT
$t0, $s5, $s5
$t0, $t0, $t0
$t0, $s6, $t0
$t1, 0($t0)
$t1
$s0, $s3, $s4
EXIT
$s0, $s1, $s2
EXIT
$s6 →
$s0, $s1, $s2
EXIT
$s0, $s3, $s4
変数名
レジスタ
f
$s0
g
$s1
h
$s2
i
$s3
j
$s4
k
$s5
番地表先頭番地
$s6
定数4
$t2
添え字
登録番地
0
L0
1
L1
2
L2
3
L3
九州大学工学部電気情報工学科
コード例: C言語の for 文(1)
1. 初期化式を評価する.
2. 条件式の値が真(0以外の整数)ならば文または中括弧の中
を実行する.偽(0)ならば文または中括弧の中を実行せずに
次に進む(=ループを終了する).
3. 文または中括弧の中を実行した後は,更新式を評価し,2. に
戻る.
for (初期化式; 条件式; 更新式)
文;
条件式が「真」の間,
繰り返し実行される
for (初期化式; 条件式; 更新式) {
文;
...
}
九州大学工学部電気情報工学科
コード例: C言語の for 文(2)
for (i = 0, j = 15; i < j; i++, j--) {
tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
i
j
a[0]
a[1]
a[2]
a[14]
a[15]
九州大学工学部電気情報工学科
コード例: C言語の for 文(3)
初期化式
条件式 FOR:
tmp = a[i]
a[i] = a[j]
a[j] = tmp
更新式
EXIT:
add
add
slt
beq
add
add
add
lw
add
add
add
lw
sw
sw
add
sub
j
…
$s0, $zero, $zero
$s1, $t4, $zero
$t0, $s0, $s1
$t0, $zero, EXIT
$t1, $s0, $s0
$t1, $t1, $t1
$t1, $s3, $t1
$s2, 0($t1)
$t2, $s1, $s1
$t2, $t2, $t2
$t2, $s3, $t2
$t3, 0($t2)
$t3, 0($t1)
$s2, 0($t2)
$s0, $s0, $t5
$s1, $s1, $t5
FOR
変数名
レジスタ
i
$s0
j
$s1
tmp
$s2
a[] 先頭番地
$s3
定数15
$t4
定数1
$t5
九州大学工学部電気情報工学科
制御の流れ
(手続き呼出)
(教科書3.6節)
手続き呼出の基本(1)
#include <stdio.h>
int add (int a, int b)
{
int c;
3, 4
a + b を計算して
c に代入
7
c の値を返す
関数 add 呼出
c に結果代入
c = a + b;
return c;
c: 7, d: 0
c, d の値を表示
}
int main ()
{
int c = 0, d = 0;
c: 7, d: 16
c = add (3, 4);
printf (”c: %d, d: %d\n”, c, d);
d = add (c * 2, 2);
printf (”c: %d, d: %d\n”, c, d);
…
}
関数 add
14, 2
a + b を計算して
c に代入
16
c の値を返す
関数 add 呼出
d に結果代入
関数 add
c, d の値を表示
caller
callee
九州大学工学部電気情報工学科
手続き呼出の基本(2)
#include <stdio.h>
callee の作業:
int add (int a , int b)
{
int c;
1.
2.
3.
c = a + b;
return c;
仮引数
caller の作業:
}
int main ()
{
int c = 0, d = 0;
実引数
c = add (3 , 4);
printf (”c: %d, d: %d\n”, c, d);
d = add (c * 2 , 2);
printf (”c: %d, d: %d\n”, c, d);
…
}
実引数の仮引数への代入.
内部の実行.
復帰: caller へのジャンプ.
1.
2.
3.
実引数式の値の計算.
呼出: callee へのジャンプ.
結果の受け取り.
caller は複数ありうるので単純
なジャンプでは caller へ復帰で
きない.
九州大学工学部電気情報工学科
手続き呼出の基本(3)
 実引数の受け渡し: レジスタ $a0~$a3 (レジスタ番号 4~7)
を使用.
 結果の受け取り: レジスタ $v0,$v1(レジスタ番号 2,3)を使
用.
 callee へのジャンプ: jal 命令を使用.
 caller へのジャンプ: jr 命令を使用.
jal 命令: レジスタ $ra(レジスタ番号 31)に jal 命令直後の命令
の番地(= PC + 4)を格納し,ラベルで指定される callee へジャン
プ.復帰時は jr 命令で $ra が格納する番地にジャンプ.
jal
jr
callee
$ra
# callee 呼出
# caller へ復帰
九州大学工学部電気情報工学科
手続き呼出の基本(4)
caller 側のコード
int main ()
{
…
c = add (3, 4);
…
d = add (c * 2, 2);
…
}
変数名
レジスタ
c
$s0
d
$s1
…
addi
addi
jal
add
…
add
addi
jal
add
…
第一実引数
$a0, $zero, 3
$a1, $zero, 4
_add
$s0, $v0, $zero
第二実引数
返り値
$a0, $s0, $s0
$a1, $zero, 2
_add
$s1, $v0, $zero
【注意】addi 命令は,レジスタと定数値を加算して,その結果をレジスタに格納
する命令である.(後述)
九州大学工学部電気情報工学科
手続き呼出の基本(5)
callee 側のコード
int add (int a , int b)
{
int c;
_add:
add
add
jr
c = a + b;
return c;
第一仮引数
$s0, $a0, $a1
$v0, $s0, $zero
$ra
第二仮引数
返り値
復帰先番地
}
変数名
レジスタ
c
$s0
caller が,呼出前に復帰先番地を $ra に設定していることに注意すること.
九州大学工学部電気情報工学科
手続き呼出とスタック(1)
int add (int a, int b)
{
return a + b;
}
 $ra が上書きされ
る.(=main に戻れ
ない!)
int dbl (int a)
{
int c;
c = add (a, a);
return c;
}
int main ()
{
int c;
…
c = dbl (100);
foo (a, 3, b, 4, c);
…
}
_add:
add
jr
_dbl:
add
 caller で使ってい
たレジスタが上書き
される.
 引数が4つ以
上ある場合は?
$v0, $a0, $a1
$ra
add
jal
add
jr
_main:
…
addi
jal
add
…
#add 第一実引数
$a0, $a0, $zero
#add 第二実引数
$a1, $a0, $zero
_add
$s0, $v0, $zero
$ra
$a0, $zero, 100
_dbl
$s0, $v0, $zero
九州大学工学部電気情報工学科
手続き呼出とスタック(2)
MIPS のレジスタ使用に関するルール(=紳士協定!)
レジスタ名
レジスタ番号
用途
$zero
0
$v0~$v1
2~3
関数の返り値
$a0~$a3
4~7
引数用
$t0~$t7
8~15
一時保存用
$s0~$s7
16~23
変数用
$t8~$t9
24~25
一時保存用
$sp
29
スタックポインタ(後述)
不可
$fp
30
フレームポインタ(後述)
不可
$ra
31
戻り番地
不可
定数値 0,不要な結果の破棄
関数呼出時のレジスタ破壊
(NA)
可
不可
可
不可
可
関数呼出時のレジスタ破壊が「不可」のレジスタは,関数呼出直前と復帰直後
の値が同じになることを,プログラマが保証しなければならない.
九州大学工学部電気情報工学科
手続き呼出とスタック(3)
上書き問題の解決策 = スタックの利用
スタック: 他のデータを後入れ先出し型(LIFO: Last-In First-Out)
で格納するデータ構造.データの追加(push),データの取り出し
(pop),最後に格納したデータの参照(top)のみが許される.
push 5
push 7
3
5
7
5
7
7
pop
push 3
pop
pop
九州大学工学部電気情報工学科
手続き呼出とスタック(4)
MIPS におけるスタック:
 メモリ領域の一部をスタックのために使用する.
 MIPS では,29番のレジスタに $sp と名前をつけ,スタックの一
番上の番地を記憶するために使用する.(スタックポインタ)
$sp
112
100
104
108
112
$sp
108
–4
+4
push yyyy
xxxx
xxxx
100
104
108
112
116
yyyy
xxxx
xxxx
pop
九州大学工学部電気情報工学科
手続き呼出とスタック(5)
手続き foo の呼出手順(不完全版):
1.
2.
3.
4.
関数呼出によって破壊されうるレジスタ($t0~$t9,$v0,$v1)
の値を push する.(後に参照するレジスタのみでよい.)
foo を呼び出す.(jal foo 命令)
foo の内部で他の関数を呼び出す場合は $ra を push する.
関数呼出によって破壊されてはならないレジスタ($a0~$a3,
$s0~$s7)の値を push する.(foo 内部で更新するレジスタの
みでよい.)
caller
callee
手続き foo からの復帰手順(不完全版):
1.
2.
3.
4.
呼出後 4 で push した値を元のレジスタに pop する.
呼出後 3 で $ra を push した場合は,その値を $ra に pop す
る.
foo を呼び出した jal 命令の次の命令にジャンプする.(jr $ra
命令)
呼出前 1 で push した値を元のレジスタに pop する.
callee
caller
九州大学工学部電気情報工学科
手続き呼出とスタック(6)
int foo (int a, int b, int c, int d, int e, int f)
{
int g, h;
…
}
スタック
$a0~$a3
… = foo (3, 8, 2, 5, 4, 6);
手続き foo の呼出手順(完全版):
1.
2.
3.
4.
5.
6.
7.
$sp
ローカル変数
(g, h)
callee 側
レジスタ保存
$ra 保存
caller 側
レジスタ保存
5番目以降の実引数を push
フレームポインタ 第5実引数(4)
caller 側レジスタ保存($t0~$t7 etc.)
第6実引数(6)
$fp
foo 呼出
$ra を push
手続きフレーム
callee 側レジスタ保存($s0~$s9 etc.)
ローカル変数のための領域をスタック上に確保
$fp をスタックフレームの底に設定.
九州大学工学部電気情報工学科
手続き呼出とスタック(7)
手続きフレームは,関数の呼出ごとに生成される.
int bar ()
{
…
}
int foo ()
{
int x, y;
…
bar ();
…
foo ();
…
}
foo () 1回目
foo () 2回目
bar ()
bar ()
foo ()
bar ()
foo ()
foo ()
foo ()
foo ()
foo ()
 呼出ごとに独立したローカル変数の実現.
 再帰呼出が可能.
九州大学工学部電気情報工学科