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

制御の流れ
（教科書3.5節～3.6節）
Copyright (C) 2002, 2004 Tsuneo Nakanishi
プログラム内蔵方式
一般的なコンピュータの内部構造
PCの指す番地から取
得した命令を解読すデコーダ
る．
PC
（主記憶上にある）次に実行
する命令の番地を記憶．
レジスタ
ALU
アドレスバス
データバス
主記憶
プログラムの命令と
データを格納．
・
・
・
Copyright (C) 2002, 2004 Tsuneo Nakanishi
ラベル名
ラベル名: 命令やデータが配置されている主記憶上の番地につ
けられた名前．
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:
ラベル定義
ラベル参照
ラベル名はアセンブラによって実際の番地に変換される．
Copyright (C) 2002, 2004 Tsuneo Nakanishi
分岐命令（１）
条件分岐命令の例:
beq
bne
$s0, $s1, L1
$s0, $s1, L2
# $s0 = $s1 なら L1 へ分岐
# $s0  $s1 なら L2 へ分岐
無条件分岐命令の例:
# L3 へ分岐
# $s0 に格納されている番地へ分岐
j
jr
L3
$s0
beq
$s0, $s1, L1
$s0 = $s1
Yes
No
次の命令
bne
$s0, $s1, L2
$s0  $s1
Yes
No
ラベルL1の番地
次の命令
ラベルL2の番地
Copyright (C) 2002, 2004 Tsuneo Nakanishi
分岐命令（２）
slt（set less than）命令：
slt
$t0, $s1, $s2
Yes
$t0 ← 1
# $s1 < $s2 ならば $t0 に 1 を設定．
# そうでなければ $t0 に 0 を設定．
$s1 < $s2
No
$t0 ← 0
Copyright (C) 2002, 2004 Tsuneo Nakanishi
分岐命令（３）
$zero レジスタ: 常に 0 が読み出されるレジスタ．（レジスタ0番）
# $s0 < $s1 なら分岐
slt
$t0, $s0, $s1
bne
$t0, $zero, L
# $s0 <= $s1 なら分岐
slt
$t0, $s1, $s0
beq
$t0, $zero, L
# $s0 > $s1 なら分岐
slt
$t0, $s1, $s0
bne
$t0, $zero, L
# $s0 >= $s1 なら分岐
slt
$t0, $s0, $s1
beq
$t0, $zero, L
Copyright (C) 2002, 2004 Tsuneo Nakanishi
コード例: C言語の goto 文
 ラベル名で指定するところに飛ぶ．
L100:
…
goto L100;
...
xxxx
L100:
j
…
xxxx
L100
Copyright (C) 2002, 2004 Tsuneo Nakanishi
コード例: C言語の if 文（１）
 式の値が真（０以外の整数）ならば else の前を実行する．式の
値が偽（０）ならば else の後を実行する．文が複数ある場合は
中括弧でくくる．
if (式)
文;
else
文;
省略可能
if (式) {
文;
...
}
else {
文;
...
}
 式の値が偽のときに特にすることがなければ，else 以降は省
略してもよい．
Copyright (C) 2002, 2004 Tsuneo Nakanishi
コード例: C言語の if 文（２）
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
Copyright (C) 2002, 2004 Tsuneo Nakanishi
コード例: C言語の if 文（３）
if (i == j)
f = g + h;
else
f = g – h;
bne
add
j
ELSE: sub
EXIT: …
$s3, $s4, ELSE
$s0, $s1, $s2
EXIT
$s0, $s1, $s3
変数名
レジスタ
f
$s0
g
$s1
h
$s2
i
$s3
j
$s4
Copyright (C) 2002, 2004 Tsuneo Nakanishi
コード例: C言語の while 文（１）
1. 条件式を評価する．
2. 条件式の値が真（０以外の整数）ならば文または中括弧の中
を実行する．偽（０）ならば文または中括弧の中を実行せずに
次に進む（＝ループを終了する）．
3. 文または中括弧の中を実行した後は 1. に戻る．
while (条件式)
文;
while (条件式) {
文;
...
}
Copyright (C) 2002, 2004 Tsuneo Nakanishi
コード例: C言語の while 文（２）
while (save[i] == k)
i = i + j;
save[i] の番地 = $s6 + $s3 * 4
WHILE: add
add
add
lw
bne
add
j
EXIT:
…
$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
Copyright (C) 2002, 2004 Tsuneo Nakanishi
コード例: C言語の switch 文（１）
 式の値と同じ値の case のところに飛ぶ．該当する case がな
い場合は default のところに飛ぶ．
switch (式) {
case 値1:
...
case 値2:
...
case 値3:
...
default:
...
}
式=値1のとき
式=値2のとき
式=値3のとき
式=その他の値のとき
省略可能
 default 以降は不要ならば省略してもよい．
Copyright (C) 2002, 2004 Tsuneo Nakanishi
コード例: C言語の switch 文（２）
 通常，switch 文の各 case のあとには break 文を入れる．
 switch 文の中括弧の中で break 文を実行すると，中括弧の残
りの実行を打ち切り，switch 文の外に飛ぶ．
switch (式) {
case 値1:
...
break;
case 値2:
...
break;
default:
...
}
式=値1のとき
式=値2のとき
式=その他の値のとき
Copyright (C) 2002, 2004 Tsuneo Nakanishi
コード例: C言語の switch 文（３）
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;
}
Copyright (C) 2002, 2004 Tsuneo Nakanishi
コード例: C言語の switch 文（４）
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
Copyright (C) 2002, 2004 Tsuneo Nakanishi
コード例: C言語の switch 文（５）
表に登録されている
番地に分岐．
添え字
登録番地
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
Copyright (C) 2002, 2004 Tsuneo Nakanishi
コード例: C言語の switch 文（６）
範囲検査
多岐分岐
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
Copyright (C) 2002, 2004 Tsuneo Nakanishi
コード例: C言語の for 文（１）
1. 初期化式を評価する．
2. 条件式の値が真（０以外の整数）ならば文または中括弧の中
を実行する．偽（０）ならば文または中括弧の中を実行せずに
次に進む（＝ループを終了する）．
3. 文または中括弧の中を実行した後は，更新式を評価し，2. に
戻る．
for (初期化式; 条件式; 更新式)
文;
for (初期化式; 条件式; 更新式) {
文;
...
}
Copyright (C) 2002, 2004 Tsuneo Nakanishi
コード例: C言語の for 文（２）
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]
Copyright (C) 2002, 2004 Tsuneo Nakanishi
コード例: C言語の for 文（３）
初期化式
条件式
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
Copyright (C) 2002, 2004 Tsuneo Nakanishi
手続き呼出の基本（１）
#include <stdio.h>
int add (int a, int b)
{
int c;
c = a + b;
return c;
}
3, 4
a + b を計算して
c に代入
7
c の値を返す
関数 add 呼出
c に結果代入
関数 add
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);
…
}
14, 2
a + b を計算して
c に代入
16
c の値を返す
関数 add 呼出
d に結果代入
関数 add
c, d の値を表示
caller
callee
Copyright (C) 2002, 2004 Tsuneo Nakanishi
手続き呼出の基本（２）
#include <stdio.h>
callee の作業：
int add (int a , int b)
{
int c;
1. 実引数の仮引数への代入．
2. 内部の実行．
3. 復帰： caller へのジャンプ．
c = a + b;
return c;
仮引数
}
caller の作業：
int main ()
{
int c = 0, d = 0;
1. 実引数式の値の計算．
2. 呼出： callee へのジャンプ．
3. 結果の受け取り．
実引数
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 は複数ありうるので単純
なジャンプでは caller へ復帰で
きない．
Copyright (C) 2002, 2004 Tsuneo Nakanishi
手続き呼出の基本（３）
 実引数の受け渡し：レジスタ $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 へ復帰
Copyright (C) 2002, 2004 Tsuneo Nakanishi
手続き呼出の基本（４）
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 命令は，レジスタと定数値を加算して，その結果をレジスタに格納
する命令である．（後述）
Copyright (C) 2002, 2004 Tsuneo Nakanishi
手続き呼出の基本（５）
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 に設定していることに注意すること．
Copyright (C) 2002, 2004 Tsuneo Nakanishi
手続き呼出とスタック（１）
int add (int a, int b)
{
return a + b;
}
 $ra が上書きされ
る．（＝main に戻れ
ない！）
int dbl (int a)
{
int c;
c = add (a, a);
return c;
}
 caller で使ってい
int main ()
{
たレジスタが上書き
int c;
される．
…
c = dbl (100);
 引数が4つ以
foo (a, 3, b, 4, c);
…
上ある場合は？
}
_add:
add
jr
$v0, $a0, $a1
$ra
_dbl:
add
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
Copyright (C) 2002, 2004 Tsuneo Nakanishi
手続き呼出とスタック（２）
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)
可
不可
可
不可
可
関数呼出時のレジスタ破壊が「不可」のレジスタは，関数呼出直前と復帰直後
の値が同じになることを，プログラマが保証しなければならない．
Copyright (C) 2002, 2004 Tsuneo Nakanishi
手続き呼出とスタック（３）
上書き問題の解決策＝スタックの利用
スタック：他のデータを後入れ先出し型（LIFO: Last-In First-Out）
で格納するデータ構造．データの追加（push），データの取り出し
（pop），最後に格納したデータの参照（top）のみが許される．
push 5
push 7
3
5
7
5
7
7
pop
push 3
pop
pop
Copyright (C) 2002, 2004 Tsuneo Nakanishi
手続き呼出とスタック（４）
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
Copyright (C) 2002, 2004 Tsuneo Nakanishi
手続き呼出とスタック（５）
手続き foo の呼出手順（不完全版）：
1. 関数呼出によって破壊されうるレジスタ（$t0～$t9，$v0，$v1）
の値を push する．（後に参照するレジスタのみでよい．）
2. foo を呼び出す．（jal foo 命令）
3. foo の内部で他の関数を呼び出す場合は $ra を push する．
4. 関数呼出によって破壊されてはならないレジスタ（$a0～$a3，
$s0～$s7）の値を push する．（foo 内部で更新するレジスタの
みでよい．）
caller
callee
手続き foo からの復帰手順（不完全版）：
1. 呼出後 4 で push した値を元のレジスタに pop する．
2. 呼出後 3 で $ra を push した場合は，その値を $ra に pop す
る．
3. foo を呼び出した jal 命令の次の命令にジャンプする．（jr $ra
命令）
4. 呼出前 1 で push した値を元のレジスタに pop する．
callee
caller
Copyright (C) 2002, 2004 Tsuneo Nakanishi
手続き呼出とスタック（６）
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 をスタックフレームの底に設定．
Copyright (C) 2002, 2004 Tsuneo Nakanishi
手続き呼出とスタック（７）
手続きフレームは，関数の呼出ごとに生成される．
int bar ()
{
…
}
int foo ()
{
int x, y;
…
bar ();
…
foo ();
…
}
foo () 1回目
foo () 2回目
bar ()
bar ()
foo ()
bar ()
foo ()
foo ()
foo ()
foo ()
foo ()
 呼出ごとに独立したローカル変数の実現．
 再帰呼出が可能．
Copyright (C) 2002, 2004 Tsuneo Nakanishi

Download Report