反復構造と配列 while文（for文）プログラムの制御構造（C言語）

反復構造と配列
while文（for文）
制御構造を実現するための命令
• 分岐命令（条件分岐命令，無条件分岐命令）
beq 命令 bne 命令 b 命令
• 比較命令
slt 命令
slti 命令
プログラムの制御構造（C言語）
条件判定： if - then - else 型
条件判定： if - then 型
条件
不成立
成立
条件
不成立
成立
命令列
命令列
1
1
命令列
2
プログラムの制御構造（C言語）
繰返し： while 型
繰返し： for 型
（ for 文はwhile型の特殊な場合 )
条件
for ( n=0; n < 100 ; n++) {
命令列 ;
}
不成立
成立
命令列
n=0 ;
while ( n < 100 ) {
命令列 ;
n=n+1 ;
}
繰返し： while 型
C 言語での記述
while （条件） {
if 文で記述すると
L1: if （条件不成立） goto L2
文1 ;
文2 ;
・・・
}
文1 ;
文2 ;
・・・
goto L1;
L2:
goto は無条件分岐命令(b命令)に対応
条件式が成立している間
{ 文1;
文2;
…
}
を繰り返す
2
1: n=0 ;
2: while ( n<100 ) {
3:
文1 ;
4:
文2 ;
5:
・・・
6:
n=n +1;
7:
}
n<100 なら $t0=1
n≧100なら $t0=0
したがって，
$t0=0 ならば while 文
から脱出する
繰返し（1）
1
sw $zero, 0(gp)
#n←0
2 L1:
lw $s0, 0($gp)
# $s0 ← n
3
slti $t0, $s0, 100
# $s0と100 との比較
4
beq $t0, $zero, exit
5
（文1, 文2, ･･･, の処理）
6
lw $s0, 0($gp)
# $s0 ← n
7
addi $s0, $s0, 1
# $s0 ← $s0 + 1
8
sw $s0, 0($gp)
# n ← $t1
9
b L1
# L1へ戻る
10 exit:
for文では
for (n=0; n < 100 ; n++) {
文1 ;
文2 ;
・・・ ;
}
1: n=0 ;
2: while ( n<p ) {
3:
文1 ;
4:
文2 ;
5:
・・・
6:
n=n +1;
7:
}
n<p なら $t0=1
n≧p なら $t0=0
したがって，
$t0=0 ならば while 文
から脱出する
for文では
$gp
n
繰返し（2）
1
#n←0
sw $zero, 0(gp)
# $s0 ← n
2 L1: lw $s0, 0($gp)
3
lw $s1, 4($gp)
# $s1 ← p
4
slt $t0, $s0, $s1
# $s0と$s1との比較
5
beq $t0, $zero, exit
6
（文1, 文2, ･･･, の処理）
7
lw $s0, 0($gp)
# $s0 ← n
8
addi $s0, $s0, 1
# $s0 ← $s0 + 1
9
sw $s0, 0($gp)
# n ← $t1
10
b L1
11 exit:
for (n=0; n < p ; n++) {
文1 ;
文2 ;
・・・ ;
}
# L1へ戻る
$gp
3
n
p
配列（array）
変数:
一つの変数に一つの値を保持する
配列:
一つの配列に同じ型の値を複数個
保持することができる
配列名
添え字（subscript）
Aという名前の配列
第0要素
C言語での宣言
A [0] 整数
A [1] 整数
int A[5] ;
A [2] 整数
第2要素
A [3] 整数
A [4] 整数
第3要素
第1要素
第4要素
5個のデータ（A[0]~A[4]）の平均値を
変数aveに求めるCプログラム
int
int
int
int
average ;
sum ;
A[5] ;
n;
/* 平均値 */
/* 総和 */
/* データ */
/* データ数 */
n=5；
sum = 0 ;
i=0;
while （ i < n ) {
sum = sum + A[i] ；
i = i+1 ;
}
average = sum / n ;
4
/* 総和を求める */
アセンブリ言語には配列の機能はない
→ 自前で実現する
配列の実現
z 変数と同様に連続した主記憶の領域に要素を配置する
例：配列Aを10000番地
から配置したとすると，
A[0] は10000 番地
A[1] は10004 番地
A[2] は10008 番地
A[3] は10012 番地
番地
配列の要素も語（word）単位で
アクセスする
10000 10000 10001 10002 10003
10004 10004 10005 10006 10007
10008 10008 10009 10010 10011
10012 10012 10013 10014 10015
…
主記憶の番地
（byteアドレス）
配列要素のアドレス計算
a：配列の先頭番地
一つの配列要素は1語（4byte）
i ：要素番号（添え字）
i 番目の要素 A[i] は a+4×i 番地に配置される
a 番地
a+4 番地
a+8 番地
A[0]
A[1]
A[2]
…
…
A[ i ]
…
…
A[99]
a+ 4×i 番地
a+ 4×99 番地＝ a+ 396 番地
5
配列要素のアドレス計算の例
問配列Aが24000番地から配置されている。
配列要素 A[12] は何番地になるか?
答 24000 + 4×12 = 24048 番地
A[0] 24000 24000 24001 24002 24003
A[1] 24004 24004 24005 24006 24007
12 番目
…
A[12] 24048 24048 24049 24050 24051
※ 以下の例題では，配列の先頭番地は$t7に与えられているとする
代入文の例 A[12] = A[8] + x ;
※ 配列 A の先頭番地は$t7に与えられているとする
1
lw $s0, 32($t7)
# $s0 ← A[8] オフセットは 4×8
2
lw $s1, 0($gp)
# $s1 ← x
3
add $t0, $s0, $s1
# $t0 ← $s0+$s1 ( = A[8]+x )
4
sw $t0, 48($t7)
# A[12] ← $t0 オフセットは 4×12
オフセットは添え字の4倍を指定する
$gp
$t7
x
A[0]
A[1]
A[2]
A[3]
…
…
6
代入文の例 A[i] = 8*A[i] ;
※ 配列 A の先頭番地は$t7に与えられているとする
1
2
3
4
5
6
lw $s0, 0($gp)
sll $t1, $s0, 2
add $t0, $t7, $t1
lw $s1, 0($t0)
sll $t2, $s1, 3
sw $t2, 0($t0)
i は変数であること
に注意 !
# $s0 ← 変数 i の値
# $t1 ← 4×i
# $t0 ← A[i] のアドレス
# $s1 ← A[i] の値
# $t2 ← 8*$s1
# A[i] ← $t2
$gp
$t7
i
x
A[0]
A[1]
A[2]
A[3]
…
…
$t0 には A[i] のアドレスが保持されている（3行目）
代入文の例 A[i] = A[i] + x ;
※ 配列 A の先頭番地は$t7に与えられているとする
1
2
3
4
5
6
lw $s0, 0($gp)
sll $t1, $s0, 2
add $t0, $t7, $t1
lw $s1, 0($t0)
lw $s2, 4($gp)
add $s1, $s1, $s2
7
sw $s1, 0($t0)
# $s0 ← 変数 i の値
# $t1 ← 4×i
# $t0 ← A[i] のアドレス
# $s1 ← A[i] の値
# $s2 ← 変数 x の値
# $s1 ← $s1+$s2
# A[i] ← $s1
i は変数であること
に注意 !
$gp
$t7
i
x
A[0]
A[1]
A[2]
A[3]
…
$t0 には A[i] のアドレスが保持されている（3行目）
7
…
最大値検出のプログラム
配列A[0]～A[99]の中から最大値を見つける
考え方：
変数maxに仮の最大値としてA[0]を代入する
maxとA[1]を比較して，A[1]が大きければmaxにA[1]を代入する
maxとA[2]を比較して，A[2]が大きければmaxにA[2]を代入する
maxとA[3]を比較して，A[3]が大きければmaxにA[3]を代入する
……
(99) maxとA[99]を比較して，A[99]が大きければmaxにA[99]を代入する
(0)
(1)
(2)
(3)
(0) 変数maxに仮の最大値としてA[0]を代入する
(1) i=1 から i=99 まで次のことを繰り返す
● maxとA[ i ]を比較して，A[ i ]が大きければmaxにA[ i ]を代入する
if ( max < A[ i ] ) max = A[ i ] ;
C言語で書くと...
max=A[0] ;
i=1 ;
while ( i < 100) {
if ( max < A[i] ) max = A [i] ;
i = i+1;
}
8
①
条件文 if (max<A[i]) max = A[i] ;
1
lw $s0, 4($gp)
# $s0 ← 変数 max の値
2
lw $s1, 0($gp)
# $s1 ← 変数 i の値
3
sll $t0, $s1, 2
# $t0 ← 4×i
4
add $t0, $t0, $t7
# $t0 ← A[i] のアドレス
5
lw $s2, 0($t0)
# $s2 ← A[i] の値
6
slt $t1, $s0, $s2
# max < A[i] なら $t1 ← 1
7
beq $t1, $zero, L2
# $t1 が 0 ならば，L2 へ
8
sw $s2, 4($gp)
# max ← A[i]
9 L2:
$gp
$t7
i
max
A[0]
A[1]
A[2]
A[3]
…
…
max < A[i] なら $t1=1
max≧A[i] なら $t1=0
したがって，
$t1=0 ならば，
if 文から脱出する
中間試験3 出題問題例
例1 次のCプログラムの断片は，64個の要素をもつ配列Aの中に，変数 x
の値に等しい要素が何個あるかを数え，その個数を変数 n に格納するプ
ログラム部分である。このプログラム部分に対応するアセンブリ言語の命
令列を示せ。
$gp →
i
n
x
$t7 → A[0]
i = 63 ;
n=0;
while ( i >= 0 ) {
if ( A [ i ] = = x ) n = n + 1 ;
i=i－1;
}
A[1]
A[2]
．
．
．
．
．
．
A[63]
図1 変数と配列の配置
例2 次のCプログラムの断片は，64個の要素をもつ配列Aの中に，変数 x
の値以上の値をもつ要素が何個あるかを数え，その個数を変数 n に格納
するプログラム部分である。このプログラム部分に対応するアセンブリ言
語の命令列を示せ。
i =0;
n=0;
while ( i != 64 ) {
if ( A [ i ] >= x ) n = n + 1 ;
i=i+1;
}
9
※ 変数領域の先頭番地は
$gp が保持し，配列Aの先頭
番地は $t7 が保持しているも
のとする。
最大値検出のプログラム
lw $t0, 0($t7)
# $t0 ← A[0]
2
sw $t0, 4($gp)
# max ← $t0
3
addi $t0, $zero, 1
# $t0 ← 1
4
sw $t0, 0($gp)
1
1: max=A[0] ;
2: i=1 ;
3: while (i<100) {
4: if ( max < A[i] )
5:
max = A[i] ;
6:
i = i +1;
7:
}
$s1<100 なら $t2=1
$s1≧100なら $t2=0
したがって，
$t2=0 ならば while 文
から脱出する
$s2<$S1 なら $t1=1
$s2≧$s1なら $t1=0
したがって，
$t1=0 ならば
max←A[i] をスキップ
max=A[0]
i=1
# i ← $t0
5 L1: lw $s1, 0($gp)
# $s1 ← i
6
slti $t2, $s1, 100
# $s1と100 との比較
7
beq $t2, $zero, exit
# $t2=0 ならばwhile文から脱出
8
lw $s0, 4($gp)
# $s0 ← 変数 max の値
9
lw $s1, 0($gp)
# $s0 ← i
10
sll $t0, $s1, 2
# $t0 ← 4×i
11
add $t0, $t0, $t7
# $t0 ← A[i] のｱﾄﾞﾚｽ
12
lw $s2, 0($t0)
# $s2 ← A[i] の値
13
slt $t1, $s0, $s2
# max < A[i] ならば $t1 ← 1
14
beq $t1, $zero, L2
# $t1 が 0 ならばL2 へ
15
sw $s2, 4($gp)
# max ← A[i]
16 L2: addi $s1, $s1, 1
# $s1 ← $s1+1
17
sw $s1, 0($gp)
# i ← $s1
18
b L1
19 exit:
$gp
$t7
※ 9行目のlw命令はなくてよい
（5行目ですでに $s1 には i の値がロードされている）
i
max
A[0]
A[1]
A[2]
A[3]
…
…
変数領域
10

Download Report