ディジタル回路 第1回 ガイダンス、CMOSの基本回路

計算機構成 第7回
サブルーチンコールとスタック
テキストp85-90
情報工学科
天野英晴
サブルーチンコール
メインルーチン
A
サブルーチンは呼ばれた所に
戻っていく
違った場所で呼べる
call A
ソフトウェアのモジュール化が可能
return
現在のプログラムでは不可欠
call A
サブルーチンコール命令の
実装における選択
→戻り番地(pc+1)を
どこにしまうか?
Jump and Link
• 戻り番地を最大番号のレジスタに保存
– POCOの場合r7
– 古典的な手法でマインフレーム時代に使われた
• Branch and Link命令
– RISCで最も良く使われる方式
JAL X : pc←pc+1+X, r7←pc+1
10101 XXXXXXXX
飛ぶ範囲はJMPと同じく11ビット(-1024~1023)
議論1:サブルーチンの入れ子(ネスト)に対応しない
議論2:r7にしまうのは命令の直交性を損ねる(格好わるい)
2乗を計算する例
end:
LDIU r0,#0
LD r1,(r0)
MV r2,r1 r1とr2に同じ値をセットする
JAL mult
JMP end
// Subroutine Mult r3 ← r1×r2 ここでr2は破壊される
mult: LDIU r3,#0
loop: ADD r3,r1
ADDI r2,#-1
BNZ r2, loop
JR r7
POCOのサブルーチンコール
メインルーチン
A
JAL A
リターン命令にはJR r7が利用可能
JAL B? ここで疑問:
サブルーチンの中で別のサブルーチン
を呼ぶとr7が壊れて戻れなくなるのでは?
JR r7
JAL A
その通り!
しかし他にも壊れては困るレジスタは
あるはず
→保存するためにスタックが必要
スタック
データを積む棚
push操作でデータを積み
pop操作で取り出す
• LIFO(Last In First Out)、FILO(First In Last Out)とも呼ばれる
• 演算スタックとは違う(誤解しないで!)
• 主記憶上にスタック領域が確保される
C
C
push
B
A
pop
C
B
A
B
A
Bでは r0,r1が
壊れる
スタックを使った入れ子構造への対応
B push r0, push r1
メインルーチン
A
push r0, push r7
JAL B
JAL A
JAL C
r7
r0
r1
r0
r7
r0
pop r1, pop r0
JR r7
pop r7, pop r0
JR r7
JAL A
Cでは r1,r2が
壊れる
Aでは r0,r7が
壊れる
壊れるレジスタをサブルーチンの
入り口でpushして保存し、
出口でpopして復帰
→ 呼ぶ方で保存する方法もある
C
r2
r1
r7
r0
push r1, push r2
pop r2, pop r1
JR r7
スタックの実現(push)
• r6をスタックポインタとする
• スタックポインタをマイナスしてからSTする
push 0、push 1は
ADDI r6,#-1
ST r0,(r6)
ADDI r6,#-1
ST r1,(r6)
r1
r0
スタック領域
r6
r6
r1
r0
スタックの実現(pop)
• スタック領域はメモリの番地の小さい方に伸びる→昔からの習慣
• pop操作は、LDしてからスタックポインタを+する。
pop 1、pop 0は
LD r1(r6)
ADDI r6,#1
LD r0,(r6)
ADDI r6,#1
r6
r1
r0
r1
r0
r6
2乗を計算する例
r2を破壊しないサブルーチンコール
r6はメインルーチンで初期化する必要がある
// Subroutine Mult r3 ← r1×r2
mult: ADDI r6,#-1
ST r2,(r6)
LDIU r3,#0
loop: ADD r3,r1
ADDI r2,#-1
BNZ r2, loop
LD r2,(r6)
ADDI r6,#1
JR r7
JALを巡る議論
• 戻り番地を汎用レジスタに格納する方針
– どっちみちスタックに汎用レジスタにしまう
– ならば入れ子になるときには、r7もついでにしまってやれ
ば良い
– システムスタックを持っていてCall時にこれにしまう方法
(IA32などの方法)と比べて劣ってはいない→むしろ不必
要なメモリ読み書きが減る
• ではr7に決めちゃうのはどうなの?
– 任意のレジスタにしまうことができても意味がない
– JALはできるだけ遠くに飛びたいのでレジスタのフィール
ドはないほうが良い
– 多少の格好の悪さは我慢しよう!
JAL命令のVerilog記述
• pcをr7に保存する
assign rf_c = ld_op ? ddatin: jal_op ? pc+1: alu_y;
assign rwe = ld_op | alu_op…| jal_op;
assign cadr = jal_op? 3’b111 : rd;
rfile
rfile_1(.clk(clk), .a(rf_a), .aadr(rd), .b(rf_b), .badr(
rs), .cadr(cadr), .we(rwe);
今までと異なりレジスタファイルのaadr=cadrではなく
なる。この二つを分離する必要がある
JALのVerilog記述
飛び方はJMPと同じ
always @(posedge clk or negedge rst_n)
begin
if(!rst_n) pc <= 0;
else if ((bez_op & rf_a == 16’b0) | (bnz_op & rf_a != 16’b0) |
(bpl_op & ~rf_a[15]) | (bmi_op & rf_a[15]))
pc<=pc+{{8imm[7]}},imm}+1;
else if (jmp_op| jal_op)
pc <= pc +{{5{idatain[10]}},idatain[10:0]}}+1;
else if(jr_op)
pc <= rf_a;
else
pc<=pc+1;
end
R型命令一覧
00000------00000
NOP
MV rd,rs
rd← rs
00000dddsss00001
AND rd,rs
rd← rd AND rs
00000dddsss00010
OR rd,rs
rd← rd OR rs
00000dddsss00011
SL rd
rd← rd<<1
00000ddd---00100
SR rd
rd← rd>>1
00000ddd---00101
ADD rd,rs
rd← rd + rs
00000dddsss00110
SUB rd,rs
rd← rd - rs
00000dddsss00111
ST rd,(ra)
(ra)← rd
00000dddaaa01000
LD rd,(ra)
rd← (ra)
00000dddaaa01001
JR rd
pc ← rd
00000ddd---01010
I型命令一覧
LDI rd,#X
rd← X(符号拡張)
01000dddXXXXXXXX
LDIU rd,rs
rd← X(ゼロ拡張)
01001dddXXXXXXXX
ADDI rd,#X
rd←rd+X(符号拡張)
01100dddXXXXXXXX
ADDIU rd,#X
rd←rd+X(ゼロ拡張)
01101dddXXXXXXXX
LDHI rd,#X
rd←{X,0}
01010dddXXXXXXXX
BEZ rd,X
if(rd=0) pc←pc+X+1
10000dddXXXXXXXX
BNZ rd,X
if(rd≠0) pc←pc+X+1
10001dddXXXXXXXX
BPL rd,X
if(rd>=0) pc←pc+X+1
10010dddXXXXXXXX
BMI rd,X
if(rd<0) pc←pc+X+1
10011dddXXXXXXXX
J型命令一覧
JMP #X
JAL #X
pc←pc+X+1
10100XXXXXXXXXXX
pc←pc+X+1,
r7←pc+1
10101XXXXXXXXXXX
演習
1.multを利用して0番地の数の3乗を計算せよ
2.JALR rdは、JAL同様r7に戻り番地をしまっ
てJR同様rdの中身の番地にそのまま飛ぶ命
令である。これを実装せよ。
JALR rd 00000ddd---11000