制御の流れ (分岐命令) (教科書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 () 呼出ごとに独立したローカル変数の実現. 再帰呼出が可能. 九州大学工学部電気情報工学科
© Copyright 2024 ExpyDoc