反復構造と配列 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
© Copyright 2025 ExpyDoc